重建二叉树

题目如下：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：我们根据前序和中序可以确定根节点和左右子树

从上面可知，题目中前序遍历的第一个节点{1}一定是这棵二叉树的根节点，根据中序遍历序列，可以发现中序遍历序列中节点{1}之前的{4,7,2}是这棵二叉树的左子树，{5,3,8,6}是这棵二叉树的右子树。然后，对于左子树，递归地把前序子序列{2,4,7}和中序子序列{4,7,2}看成新的前序遍历和中序遍历序列。此时，对于这两个序列，该子树的根节点是{2}，该子树的左子树为{4,7}、右子树为空，如此递归下去（即把当前子树当做树，又根据上述步骤分析）。{5,3,8,6}这棵右子树的分析也是这样。
代码：

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution{

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

if(pre == null || in == null || pre.length != in.length){    //当前序或中序为空 或者前序与中序的长度不相等时，返回null
return null;
}
return construct(pre, 0, pre.length-1, in, 0, in.length-1);    
}

/**
      * 
      * @param pre    前序遍历
      * @param ps    前序遍历的开始位置
      * @param pe    前序遍历的结束位置
      * @param in    中序遍历
      * @param is    中序遍历的开始位置
      * @param ie    中序遍历的结束位置
      * @return        数的根节点
      */

private TreeNode construct(int []pre,int ps, int pe, int []in, int is, int ie){
if(ps > pe) return null;
int value =pre[ps];
int index =is;  //
while(index <= ie && value != in[index]){
index++;
}
if(index > ie){
throw new RuntimeException("Invalid Iuput!");
}
TreeNode node = new TreeNode(value);
node.left = construct(pre,ps+1,ps+index-is,in,is,index-1);   //左子树的前序遍历：遍历左子树的开端 结尾 ； 中序遍历 开端和结尾
node.right = construct(pre, ps+index-is+1,pe,in, index+1,ie); //右子树的前序遍历：
return node;
}
private void printTree(TreeNode root) {
if(root != null) {
printTree(root.left);
System.out.println(root.val + " ");
printTree(root.right);
}
}

}

注解如图