Problem #106: Construct Binary Tree from Inorder and Postorder Traversal

Intuition & Strategy Breakdown

Last element of postorder is root. Locate root in inorder list to partition left and right subtrees, recursively constructing tree.

Python Solution

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        idx_map = {val: i for i, val in enumerate(inorder)}
        self.post_idx = len(postorder) - 1
        
        def helper(left, right):
            if left > right:
                return None
            
            root_val = postorder[self.post_idx]
            root = TreeNode(root_val)
            self.post_idx -= 1
            
            # Process right subtree first!
            root.right = helper(idx_map[root_val] + 1, right)
            root.left = helper(left, idx_map[root_val] - 1)
            
            return root
            
        return helper(0, len(inorder) - 1)

Java Solution

class Solution {
    int post_idx;
    Map idx_map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        post_idx = postorder.length - 1;
        for (int i = 0; i < inorder.length; i++) {
            idx_map.put(inorder[i], i);
        }
        return helper(0, inorder.length - 1, postorder);
    }

    private TreeNode helper(int left, int right, int[] postorder) {
        if (left > right) return null;

        int root_val = postorder[post_idx--];
        TreeNode root = new TreeNode(root_val);

        root.right = helper(idx_map.get(root_val) + 1, right, postorder);
        root.left = helper(left, idx_map.get(root_val) - 1, postorder);

        return root;
    }
}