题解 | JAVA 分治 #重建二叉树# [P0]

递归, 分治

跟精华解法一样思路，通过preOrder找root，inOrder找左右subtree的size.
唯一不一样的就是用HashMap存inOrder的[val -> index]。这样跑起来快很多。
时间 O(n): 每个node都会call一次build()
空间 O(n): 系统栈上worst-case最多n个node，hashMap也是O(n)

import java.util.*;

public class Solution {
    // val -> idx in vin
    Map<Integer, Integer> vinMap = new HashMap<>();
    // 存个global 省点笔墨
    int[] _pre, _vin;
  
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
      if (pre.length == 0) return null;
      _pre = pre; _vin = vin;
      
      // 将vin的val:idx存入HashMap方便O(1)查找
      for (int i=0; i < vin.length; i++) {
        vinMap.put(vin[i], i);
      }
      return build(0, pre.length-1, 0, vin.length-1);
    }
  
    // Build the tree represented by pre[preS, preE] and vin[inS, inE]
    TreeNode build(int preS, int preE, int inS, int inE) {
      // 每次分治的subtree的root就是pre[PreS]
      TreeNode root = new TreeNode(_pre[preS]);
      // basecase
      if (preS == preE) return root;
      
      // 找到root所对应的vin的idx，目的是求出left和right的subtree size
      int rootVinIdex = vinMap.get(_pre[preS]);
      int leftSize = rootVinIdex - inS;
      int rightSize = inE - rootVinIdex;
      
      // 这里必须check 不然空的一边会越界。放basecase里check也行
      if (leftSize > 0)
        root.left = build(preS+1, preS + leftSize, inS, rootVinIdex-1);
      if (rightSize > 0)
        root.right = build(preS + leftSize + 1, preE, rootVinIdex+1, inE);
      return root;
    }
}