NeetCode #415LC-431HardTreesNC Algo100
← Back to All Problems#415 · #431 · Encode N-ary Tree to Binary Tree(将 N 叉树编码为二叉树)
📌 Problem Statement & Constraints
Design an algorithm to convert an N-ary tree into a binary tree and back. The binary tree must follow the left-child, right-sibling representation. Constraints: the number of nodes is in
[0, 10^4], 0 <= Node.val <= 10^4, the depth is at most 1000.💡 Core Algorithmic Approaches
- The left-child/right-sibling encoding maps an N-ary node to a binary node whose left pointer is the first child and whose right pointer is the next sibling.
- Encoding: create a binary node, encode the first child as
left, then chain the remaining children along therightpointers of that left subtree. - Decoding: the
leftsubtree is the first child, and followingrightpointers from it enumerates the siblings. - The mapping is a bijection, so the round trip is exact.
💻 Benchmark Python3 Implementation
class Codec:
def encode(self, root: "Optional[Node]") -> Optional[TreeNode]:
if not root:
return None
node = TreeNode(root.val)
if root.children:
node.left = self.encode(root.children[0]) # first child
# chain the remaining children as right siblings
cur = node.left
for c in root.children[1:]:
cur.right = self.encode(c)
cur = cur.right
return node
def decode(self, data: Optional[TreeNode]) -> "Optional[Node]":
if not data:
return None
node = Node(data.val, [])
cur = data.left # first child
while cur:
node.children.append(self.decode(cur))
cur = cur.right # next sibling
return node⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) for both directions.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Putting all children on the left spine: only the first child goes to
left; the rest are siblings reached viaright. - Forgetting to advance
cur: all siblings would overwrite the samerightpointer. - Decoding the
rightpointers as children: they represent siblings, so they must be appended to the same parent's children list. - Assuming the round trip preserves node identity: only the structure and values are preserved.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.