二叉树模板--剑指offer第4题
来，我们来做题！
剑指offer第4题：
函数签名是：
pre是前序遍历 in是中序遍历public TreeNode reConstructBinaryTree(int [] pre,int [] in)
二叉树的题解法基本就是递归。这题我们也用递归。首先回答两个问题：每次递归做什么？什么条件退出？
每次递归做什么呢？了解前序遍历的同学会知道，前序遍历的结果根节点在左右节点的前面。而中序遍历呢？左节点在根结点左边，右节点在根节点右边。因此二者联系起来就应该满足：举个例子：拿前序遍历结果的第1个元素A，去中序遍历的结果中确定位置，那么这个位置的前面节点就是元素A的左节点，这个位置的后面节点就是元素A的右节点。这样我们就能每次递归构建出一个节点(包含左右子节点)，因此可以写出：
int index = 0;for(int i = 0; i < in.length; i++){找到中序遍历中 和 前序遍历相同的元素if(in[i] == pre[0]){index = i;break;}}根据找到的元素新建节点。TreeNode root = new TreeNode(pre[0]);
什么条件退出呢？很明显当我们每次遍历的前序或者中序数组长度为0的时候退出，当数组长度为1的时候，直接新建节点返回，不需要进行上述步骤。可以写出：
if(pre.length == 0){return null;}if(pre.length == 1){return new TreeNode(pre[0]);}
下面我们套模板
特点：在你需要返回一个二叉树的节点的时候，你必须构造这个二叉树节点，同时需要构建该节点的左右节点：root.left = , root.right = 这种赋值操作是必须要有的，然后返回构造的节点。同时退出条件一般都会有if(root == null) return null;因此就能写出：
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {if(pre.length == 0){return null;}if(pre.length == 1){return new TreeNode(pre[0]);}int index = 0;for(int i = 0; i < in.length; i++){if(in[i] == pre[0]){index = i;break;}}TreeNode root = new TreeNode(pre[0]);该左节点应该为中序遍历的的 元素A的左边root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,index+1),Arrays.copyOfRange(in,0,index));该左节点应该为中序遍历的的 元素A的右边root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,index+1,pre.length),Arrays.copyOfRange(in,index+1,in.length));返回root给上一层递归return root;}