106. Construct Binary Tree from Inorder and Postorder Traversal根据后中序数组恢复出原来的树

［抄题］：

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

距离太远就要相加。相同的题还是一起做比较好，隔一段时间再去理解实在太心累了。

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

int idx = map.get(posorder[posStart]); 从postorder中取出index作为后续使用才行

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

比较远时，加上中-右 = inidx - inend

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

都怪recursive不好跑case，算了，距离太远就要相加。

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
  
    public TreeNode buildTree(int[] inorder, int[] posorder) {
        //corner case
        if (inorder == null || posorder == null || posorder.length != inorder.length) return null;
        
        //initialization: put (posorder[i], i) into map
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < inorder.length; i++) 
            map.put(inorder[i] , i);
        
        //dfs and return
        return dfs(inorder, 0, inorder.length - 1, posorder, posorder.length - 1, 0, map);
    }
    
    public TreeNode dfs(int[] inorder, int inStart, int inEnd, 
                    int[] posorder, int posStart, int posEnd,
                   HashMap<Integer, Integer> map) {
        //exit case
        if (inStart > inEnd || posStart > posEnd) return null;
        
        //find inIdx and do dfs
        TreeNode root = new TreeNode(posorder[posStart]);
        int inIdx = map.get(root.val);
        
        //do dfs in left and right and add to root
        root.left = dfs(inorder, inStart, inIdx - 1, posorder, posStart + (inIdx - inEnd) - 1, posEnd, map);
        root.right = dfs(inorder, inIdx + 1, inEnd, posorder, posStart- 1, posEnd, map);
        
        return root;
    }
}

View Code