💬 Discord
Sign In
NeetCode #445LC-105MediumTreesBlind 75NC 150NC 250
← Back to All Problems

#445 · #105 · Construct Binary Tree from Preorder and Inorder Traversal(从前序与中序遍历序列构造二叉树)

📌 Problem Statement & Constraints

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

💡 Core Algorithmic Approaches

  1. The first element of the pre-order traversal is the root.
  2. In the in-order traversal, the root splits the array into the left and right subtrees; the size of the left part tells you how many nodes belong to the left subtree in the pre-order array.
  3. Precompute a value-to-index map for the in-order array so finding the split is O(1) instead of O(n).
  4. Recurse with the correct subarray bounds; the whole construction is O(n).

💻 Benchmark Python3 Implementation

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

        def build(pl: int, pr: int, il: int, ir: int) -> Optional[TreeNode]:
            if pl > pr:
                return None
            root = TreeNode(preorder[pl])             # pre-order's first is the root
            m = idx[root.val]                         # split point in inorder
            left_size = m - il
            root.left = build(pl + 1, pl + left_size, il, m - 1)
            root.right = build(pl + left_size + 1, pr, m + 1, ir)
            return root

        return build(0, len(preorder) - 1, 0, len(inorder) - 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 stack.

⚠️ Interview Pitfalls & Follow-ups

  • Slicing the arrays at each step: it works but allocates O(n log n) in total and hides the index arithmetic.
  • Using inorder.index(root.val): O(n) per node, giving O(n^2) overall. The precomputed map is essential.
  • Computing left_size from the wrong bounds: it is m - il, the number of in-order elements before the root.
  • Mixing up the pre-order subarray bounds: the left subtree occupies pl + 1 to pl + left_size, and the right starts at pl + left_size + 1.