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
- The last element of the post-order traversal is the root (mirroring the pre-order case, where it is the first).
- 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.
- Precompute a value-to-index map for the in-order array to make the split lookup O(1).
- 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, atpostorder[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
pltopl + left_size - 1, and the rightpl + left_sizetopr - 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.