题解 | #重建二叉树#

就是利用前序序列找到头，然后在中序序列中找到这个头的位置h，h左边就是左子树，h右边就是右子树，然后递归就可以了

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre==null||vin==null||pre.length==0||pre.length!=vin.length) return null;
        return reBuildTree(pre,0,pre.length-1,vin,0,pre.length-1);
    }
    public TreeNode reBuildTree(int[] pre,int s1,int e1,int[] vin,int s2,int v2){
        if(s1>e1||s2>v2){
            return null;
        }
        if(e1==s1||s2==v2){
            return new TreeNode(pre[e1]);
        }
        //头是pre[s1]
        TreeNode head = new TreeNode(pre[s1]);
        //在vin中找到头的下标
        int h = s2;
        while(vin[h]!=pre[s1]){
            h++;
        }
        //h-s2就能知道左子树长度了
        //左边右边重建
        int leftLen = h-s2;
        head.left = reBuildTree(pre,s1+1,s1+leftLen,vin,s2,h-1);
        head.right = reBuildTree(pre,s1+leftLen+1,e1,vin,h+1,v2);
        return head;
    }