⚡Flashcard Drill➔
NeetCode #472LC-1028HardTrees
← Back to All Problems

#472 · #1028 · Recover a Tree From Preorder Traversal(从先序遍历还原二叉树)

📌 Problem Statement & Constraints

We run a pre-order depth-first search on a binary tree, outputting D dashes followed by the node value, where D is the node's depth. Given this traversal string, reconstruct the tree. Constraints: 1 <= traversal.length <= 10^5, node values are positive integers.

💡 Core Algorithmic Approaches

  1. Parse recursively with a shared index. At each call, count the dashes to determine the depth; if it does not match the expected depth, the node is not part of this subtree.
  2. Then read the digits to get the value and recurse for the left and right children at depth + 1.
  3. The key trick is restoring the index when the dash count does not match, so the parent can try the other child.
  4. Because the traversal is a pre-order DFS, the left child is always encountered before the right, so the recursion order matches.

💻 Benchmark Python3 Implementation

class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        self.i = 0                         # shared read position

        def build(depth: int) -> Optional[TreeNode]:
            start = self.i
            while self.i < len(traversal) and traversal[self.i] == "-":
                self.i += 1
            d = self.i - start
            if d != depth:                 # not this subtree -> rewind
                self.i = start
                return None
            start = self.i
            while self.i < len(traversal) and traversal[self.i].isdigit():
                self.i += 1
            node = TreeNode(int(traversal[start:self.i]))
            node.left = build(depth + 1)
            node.right = build(depth + 1)
            return node

        return build(0)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): the index advances monotonically and each character is read a constant number of times.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Not rewinding the index when the depth does not match: the parent's second child would be skipped.
  • Assuming single-digit values: values can be multi-digit, so the digit scan is required.
  • Using split('-'): the dash count encodes the depth and cannot be recovered from a naive split.
  • Passing the depth as a global: it must be the expected depth for the current recursive call.
⚡
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