题解 | #空间复杂度更低的解法-重建二叉树#

此题的思路就是分治问题，用递归的方式解决，前面的大佬们已经讲过了。
不过有个待优化的地方，就是递归的时候数组其实可以不用拷贝，这样可以减少很多内存空间的使用。
下面贴上代码：

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int len = pre.length;
        if (len == 0) return null;
        if (len == 1) return new TreeNode(pre[0]);
        return dfs(pre, vin, 0, 0, len);
    }

    private static TreeNode dfs(int [] pre,int [] vin, int pstart, int vstart, int len){
        if (len == 0) return null;
        if (len ==  1) return new TreeNode(pre[pstart]);
        TreeNode ans = new TreeNode(pre[pstart]);
        if (len == 2){
            if (vin[vstart] == pre[pstart]){
                ans.right = new TreeNode(pre[pstart+1]);
            } else{
                ans.left = new TreeNode(pre[pstart+1]);
            }
            return ans;
        }
        int rootIndexOfVin = vstart;
        while (pre[pstart] != vin[rootIndexOfVin]){
            rootIndexOfVin++;
        }
        ans.left = dfs(pre, vin, pstart+1, vstart, rootIndexOfVin-vstart);
        ans.right = dfs(pre, vin, pstart+1+rootIndexOfVin-vstart, 1+rootIndexOfVin, len-1-rootIndexOfVin+vstart);
        return ans;

    }