题解 | #重建二叉树#

 * 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 [] vin) {
        return doReConstructBinaryTree(pre, vin, 0, pre.length - 1);
    }
    
    int l = 0;

    public TreeNode doReConstructBinaryTree(int[] pre, int[] vin, int p, int q) {
        if (pre.length == 0) {
            return null;
        }
        int h = pre[l]; // 从头到位开始记录pre数组，表示每次的头节点
        TreeNode node = new TreeNode(h);
        // 找到vin数组中pre[l]的下标。左边是node节点的左子树，右边是node节点的右子树。
        int i = -1;
        for (int n : vin) {
            i++;
            if (n == pre[l]) {
                break;
            }
        }
        l++;
        if (p == q) { // 左右范围之内剩下一个节点， 直接返回。
            return node;
        }
        if (i > p && i <= q) { // 左子树存在条件。
            node.left = doReConstructBinaryTree(pre, vin, p, i - 1);
        }
        if (i >= p && i < q) { // 右子树存在条件
            node.right = doReConstructBinaryTree(pre, vin, i + 1, q);
        }
        return node;
    }
}