题解 | #重建二叉树#

思路：

递归

1、每次递归的前序的第一个元素为根

2、在中序中找到根，将其划分为左右子树

3、对子树进行递归

实现：

利用int i，j 标记每个子树在原 vin 数组中的上下限

int h，rh，lh 标记本子树第一个前序元素在 pre 数组中的位置

优点：

不用另外开辟空间拷贝数组中的元素。

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        int j = vin.length - 1;
        if (j < 0) {
            return null;
        } else {
            int i = 0;
            int h = 0;
            return reConstructBinaryTreeRoot(pre, vin, i, j, h);
        }
    }

    private TreeNode reConstructBinaryTreeRoot(int [] pre, int [] vin, int i, int j, int h) {
        if (i > j) {
            return null;
        }
        else {
            TreeNode root = new TreeNode(pre[h]);
            int m ;
            for ( m = i; m <= j; m++) {
                if (pre[h] == vin[m]) {
                    break;
                }
            }
            int lh, rh;
            lh = h + 1;
            rh = h + m - i + 1;
            root.left = reConstructBinaryTreeRoot(pre, vin, i, m - 1, lh);
            root.right = reConstructBinaryTreeRoot(pre, vin, m + 1, j, rh);
            return root;
        }
    }
}