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

重建二叉树

http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

递归, 分治

跟精华解法一样思路,通过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;
    }
}
全部评论

相关推荐

沟头学院:无关比赛不要写,这样会显着你主次不分,比赛不要撒谎,有哪些就写那些,创新创业建议删除。技能特长可以适当夸大。
点赞 评论 收藏
分享
02-26 16:52
宜春学院 Java
Lunarloop:董事长亲自到ssob来要IM项目的技术方案来了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务