输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,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||pre.length==0) return null;
        this.pre=pre;
        this.in=in;
        return node(0, pre.length-1, 0, pre.length-1);
    }
    int[] pre;
    int[] in;

    TreeNode node(int l1, int r1, int l2, int r2){
        if(l1>r1) return null;
        if(l1==r1) return new TreeNode(pre[l1]);
        TreeNode p=new TreeNode(pre[l1]);
        int i=l2;
        for(; i<=r2; i++){
            if(in[i]==p.val) break;
        }
        p.left=node(l1+1, i-l2+l1, l2,i-1);
        p.right=node(r1-r2+i+1, r1, i+1,r2);
        return p;        
    }
}