96. Construct Binary Tree from Inorder and Postorder Traversal

Postorder visits the root last, so read postorder from the back to get roots. Each root splits inorder into left/right subtrees. Because we consume postorder in reverse (root, then right subtree, then left), build the right child before the left.

Idea

Postorder ends with the root, so scanning postorder from the end yields roots in the order root → right-subtree → left-subtree. Each root splits inorder into a left part (before it) and a right part (after it). Since we consume postorder backwards, we must build the right subtree before the left.

A value → inorder-index map makes the split O(1).

Algorithm

1. Map each inorder value to its index. Pointer p = len(postorder) - 1.
2. build(lo, hi) over an inorder range:
   • If lo > hi, return null.
   • root_val = postorder[p]; p -= 1. mid = index[root_val].
   • root.right = build(mid+1, hi) first, then root.left = build(lo, mid-1).

Worked example: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

• Root 3 (last postorder); split inorder into [9] and [15,20,7]. Rebuilds [3,9,20,null,null,15,7].

Complexity

• Time: O(n).
• Space: O(n).

import java.util.HashMap;
import java.util.Map;

class Solution {
    private int post;
    private Map<Integer, Integer> idx = new HashMap<>();

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

    private TreeNode build(int[] postorder, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        int rootVal = postorder[post--];
        TreeNode root = new TreeNode(rootVal);
        int mid = idx.get(rootVal);
        root.right = build(postorder, mid + 1, hi);
        root.left = build(postorder, lo, mid - 1);
        return root;
    }
}