NeetCode #418LC-606MediumTrees
← Back to All Problems#418 · #606 · Construct String from Binary Tree(根据二叉树创建字符串)
📌 Problem Statement & Constraints
Given the root of a binary tree, construct a string of parentheses and integers from a pre-order traversal: an empty tree is
"", a node is value(child), and omitted children are represented by omitting the parentheses. Constraints: the number of nodes is in [1, 10^4], -1000 <= Node.val <= 1000.💡 Core Algorithmic Approaches
- A pre-order walk emits the value, then the left subtree in parentheses, then the right.
- The subtlety is that a missing left child must still be emitted as
()when a right child exists, otherwise the structure is ambiguous. - A missing right child's parentheses are omitted entirely.
- So the left parentheses are emitted whenever either child exists, and the right parentheses only when the right child exists.
💻 Benchmark Python3 Implementation
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
if not root:
return ""
s = str(root.val)
# the left parentheses are needed whenever either child exists
if root.left or root.right:
s += "(" + self.tree2str(root.left) + ")"
# the right parentheses are only needed when the right child exists
if root.right:
s += "(" + self.tree2str(root.right) + ")"
return s⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node contributes a constant amount of text.
💾 Space Complexity
O(h) for the recursion stack plus O(n) for the output.
⚠️ Interview Pitfalls & Follow-ups
- Omitting the empty left parentheses when only a right child exists:
[1, null, 2]must serialise to"1()(2)", otherwise the2would be read as the left child. - Emitting
()for a missing right child: that is unnecessary and changes the string. - Using in-order or post-order: the format is specifically pre-order.
- Forgetting the empty-tree case: it must return the empty string.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.