⚡Flashcard Drill➔
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

  1. The first element of the pre-order and the last of the post-order are both the root.
  2. 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.
  3. Unlike the pre-order + in-order case, this pair of traversals does not uniquely determine the tree -- but any consistent reconstruction is accepted.
  4. 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_hi base case: without it, preorder[pre_lo + 1] would be out of range.
  • Computing left_size incorrectly: it is idx[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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems