题解 | #重建二叉树#

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    HashMap<Integer, Integer> preMapVin = new HashMap<Integer, Integer>();
    boolean[] marked;
    int j = 0;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        marked = new boolean[pre.length];
        for(int i = 0; i < pre.length; i++){
            preMapVin.put(vin[i], i);
        }
        return f(0, pre.length-1, pre, vin);
    }
    public TreeNode f(int left, int right,int[] pre, int[] vin){
      //这里left要大于right, 因为vinIndex是+1或者-1更新的。
      //如果left=right的话还要创建一个叶子节点返回。
        if(left > right){
            return null;
        }
        int vinIndex = preMapVin.get(pre[j++]);
        TreeNode node = new TreeNode(vin[vinIndex]);
        
        node.left = f(left, vinIndex-1, pre, vin);
        node.right = f(vinIndex+1, right, pre, vin);
        return node;
    }
}

前序遍历是：根节点-左子树-右子树 中序遍历是：左子树-根节点-右子树

所以我们遍历pre数组，每一次将vin化成两部分[left, vinIndex-1]、[vinIndex-1, right], vinIndex是这两部分的根节点。 其中[left, vinIndex-1]是vinIndex的左子树的所有节点，[vinIndex-1, right]是vinIndex的所有右子树节点。 每次我们递归就创建一个节点，并分别递归构建该节点的左子树和右子树，直到left > right就说明了该节点没有子树部分了，就return null；

总的来说，这题就是分治思想，将构建一棵二叉树拆成构建一棵更小的树，再由这些更小的树组成一个完整的二叉树。