106. Construct Binary Tree from Inorder and Postorder Traversal - Medium

前往題目

想法

• postorder最後面一定是root

思路

用root去定位，就可以得知左右子樹

1. dfs
2. inorder和postorder都使用雙指針
3. 當左指針超過右指針時回傳null，代表沒有子節點
4. 取得根節點的值，以及其在inorder中的index
5. 然後就可以建立父節點以及其左右子節點並遞迴呼叫

postorder只是拿來找根節點的

Code

網友解答

class Solution {
    // Val -> index
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap();
        // Build the inorder map
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode build(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
        // Base case
        if (inStart > inEnd || postStart > postEnd) return null;

        // Obtain the root from postorder
        int rootVal = postorder[postEnd];
        
        // Obtain the root index from inorder
        int rootIndex = map.get(rootVal);

        // Build the nodes
        TreeNode root = new TreeNode(rootVal);
        int leftSize = rootIndex - inStart;
        int rightSize = inEnd - rootIndex;
        root.left = build(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
        root.right = build(inorder, postorder, rootIndex + 1, inEnd, postEnd - rightSize, postEnd - 1);

        return root;
    }
}