Construct Binary Tree from Preorder and Postorder Traversal

Intuition

In preorder the root comes first and is immediately followed by the entire left subtree, so preorder's second unused value is the root of the left subtree whenever one exists. In postorder the left subtree appears as a contiguous block that ends exactly where that left-subtree root sits, so finding that value in postorder tells us how large the left subtree is. With the left size known, the remaining values split cleanly into the right subtree. Because the two traversals can describe more than one tree, we consistently treat the second preorder value as a left child, which yields one valid answer. A postorder index map plus a forward-moving preorder pointer keeps every step O(1).

Algorithm walkthrough

1. 1Map each postorder value to its index and set a preorder pointer at 0.
2. 2Define a helper that works over the postorder bounds [left, right] of the current subtree.
3. 3Return null if left exceeds right; otherwise create the root from the current preorder value and advance the pointer.
4. 4If left equals right the subtree is a single leaf, so return it immediately.
5. 5Look up the next preorder value in postorder to get mid, the last index of the left subtree, then build the left subtree from [left, mid] and the right subtree from [mid + 1, right - 1].
6. 6Return the root; the initial call covers the entire postorder range.

Implementation

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        idx = {v: i for i, v in enumerate(postorder)}
        self.pre = 0

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            root = TreeNode(preorder[self.pre])
            self.pre += 1
            if left == right:
                return root
            mid = idx[preorder[self.pre]]
            root.left = build(left, mid)
            root.right = build(mid + 1, right - 1)
            return root

        return build(0, len(postorder) - 1)