⚡Flashcard Drill➔
NeetCode #438LC-106MediumTrees
← Back to All Problems

#438 · #106 · Construct Binary Tree from Inorder and Postorder Traversal(从中序与后序遍历序列构造二叉树)

📌 Problem Statement & Constraints

Given two integer arrays inorder and postorder representing the in-order and post-order traversals of a binary tree, construct and return the tree. All values are distinct. Constraints: 1 <= inorder.length <= 3000, inorder.length == postorder.length.

💡 Core Algorithmic Approaches

  1. The last element of the post-order traversal is the root (mirroring the pre-order case, where it is the first).
  2. In the in-order array, the root splits the tree into left and right subtrees; the left subtree size tells you how to split the post-order array.
  3. Precompute a value-to-index map for the in-order array to make the split lookup O(1).
  4. The recursion builds the left subtree first, then the right, using the correct index ranges.

💻 Benchmark Python3 Implementation

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        idx = {v: i for i, v in enumerate(inorder)}   # O(1) split lookup

        def build(il: int, ir: int, pl: int, pr: int) -> Optional[TreeNode]:
            if il > ir:
                return None
            root = TreeNode(postorder[pr])             # post-order's last is the root
            m = idx[root.val]
            left_size = m - il
            root.left = build(il, m - 1, pl, pl + left_size - 1)
            root.right = build(m + 1, ir, pl + left_size, pr - 1)
            return root

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is created once and each split lookup is O(1).
💾 Space Complexity
O(n) for the index map plus O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Taking postorder[pl] as the root: in a post-order traversal the root is last, at postorder[pr].
  • Slicing the arrays: it works but allocates O(n log n) in total.
  • Using inorder.index(root.val): O(n) per node, giving O(n^2).
  • Mixing up the post-order bounds: the left subtree occupies pl to pl + left_size - 1, and the right pl + left_size to pr - 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems