NeetCode #446LC-889MediumTrees
← Back to All Problems#446 · #889 · Construct Binary Tree from Preorder and Postorder Traversal(根据前序和后序遍历构造二叉树)
📌 Problem Statement & Constraints
Given two integer arrays
preorder and postorder representing the pre-order and post-order traversal of a binary tree, construct and return the tree. If multiple trees are valid, return any of them. All values are distinct. Constraints: 1 <= preorder.length <= 30, preorder.length == postorder.length.💡 Core Algorithmic Approaches
- The first element of the pre-order and the last of the post-order are both the root.
- The element after the root in the pre-order is the root of the left subtree (assuming a left child exists); its position in the post-order tells you the left subtree's size.
- Unlike the pre-order + in-order case, this pair of traversals does not uniquely determine the tree -- but any consistent reconstruction is accepted.
- So always assume a left child when both subtrees are non-empty, which yields one valid answer.
💻 Benchmark Python3 Implementation
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
idx = {v: i for i, v in enumerate(postorder)} # O(1) split lookup
def build(pre_lo: int, pre_hi: int, post_lo: int, post_hi: int) -> Optional[TreeNode]:
if pre_lo > pre_hi:
return None
root = TreeNode(preorder[pre_lo])
if pre_lo == pre_hi:
return root # single node
left_root = preorder[pre_lo + 1]
left_size = idx[left_root] - post_lo + 1
root.left = build(pre_lo + 1, pre_lo + left_size, post_lo, post_lo + left_size - 1)
root.right = build(pre_lo + left_size + 1, pre_hi, post_lo + left_size, post_hi - 1)
return root
return build(0, len(preorder) - 1, 0, len(postorder) - 1)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is created once with O(1) split lookups.
💾 Space Complexity
O(n) for the index map plus O(h) for the recursion.
⚠️ Interview Pitfalls & Follow-ups
- Expecting a unique answer: the traversals are ambiguous for single-child nodes, so several trees are valid.
- Forgetting the
pre_lo == pre_hibase case: without it,preorder[pre_lo + 1]would be out of range. - Computing
left_sizeincorrectly: it isidx[left_root] - post_lo + 1, the size of the left subtree in the post-order array. - Assuming the tree is full: it need not be, hence the ambiguity.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.