输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

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

前序遍历的根节点在第一个，在中序遍历中找到根节点位置，其左边为左子树节点，右边为右子树节点。然后递归左右子树即可。

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return  BinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    }

    static TreeNode BinaryTree(int[] pre,int preLeft,int preRight,int[] in,int inLeft,int inRight){
        if(preLeft>preRight||inLeft>inRight){
            return  null;
        }
        TreeNode root=new TreeNode(pre[preLeft]);
        int pos=inLeft;                  //区间[inLeft,inRight]
        for(;pos<inRight;pos++){
            if(in[pos]==root.val)break;
        }
        int numLeft=pos-inLeft;
        //递归
        root.left=BinaryTree(pre,preLeft+1,numLeft+preLeft,in,inLeft,pos-1);
        root.right=BinaryTree(pre,numLeft+preLeft+1,preRight,in,pos+1,inRight);
        return root;
    }
}