重建二叉树

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

解题思路
    明白由先序遍历和中序遍历生成二叉树的过程就好了。首先找到先序遍历的第一个节点，就是根节点，然后在中序遍历中找到根节点。此时，根节点左右两边，分别是左右子树的中序遍历。再对于先序遍历，从第二个节点开始，到中序遍历中左子树的长度，就是左子树的先序遍历。同理，右子树也是一样，这是一个递归过程。

class TreeNode{
    int val=0;
    TreeNode left=null;
    TreeNode right=null;

    public TreeNode(int val){
        this.val=val;
    }
}
public class Solution {
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
         return ConstruceCore(pre,0,pre.length-1,in,0,in.length-1);
    }
     public static TreeNode ConstruceCore(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {

        if (preStart>preEnd||inStart>inEnd){
            return null;
        }

        //找到根节点
        TreeNode  root=new TreeNode(preOrder[preStart]);
        System.out.print(root.val);
        for (int i=inStart;i<=inEnd;i++){
            //在中序中找到和前序第一个位置的数
            if (inOrder[i]==preOrder[preStart]){
                //i-inStart+preStart 表示左子树长度
                root.left=ConstruceCore(preOrder,preStart+1,i-inStart+preStart,inOrder,inStart,i-1);
//                System.out.println("preEnd :"+(preStart+i-inStart));
                root.right=ConstruceCore(preOrder,i-inStart+preStart+1,preEnd,inOrder,i+1,inEnd);
//                System.out.println("preStart :"+(i-inStart+preStart+1));
            }

        }
        return root;

    }