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

  1. A pre-order walk emits the value, then the left subtree in parentheses, then the right.
  2. The subtlety is that a missing left child must still be emitted as () when a right child exists, otherwise the structure is ambiguous.
  3. A missing right child's parentheses are omitted entirely.
  4. 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 the 2 would 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems