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
- 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.
- Then read the digits to get the value and recurse for the left and right children at
depth + 1. - The key trick is restoring the index when the dash count does not match, so the parent can try the other child.
- 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.