NeetCode #409LC-1490MediumTreesNC Algo100
← Back to All Problems#409 · #1490 · Clone N-ary Tree(克隆 N 叉树)
📌 Problem Statement & Constraints
You are given a reference to an N-ary tree. Return a deep copy of the tree. Constraints: the number of nodes is in
[0, 10^4], 0 <= Node.val <= 10^4, the tree depth is at most 1000.💡 Core Algorithmic Approaches
- A recursive clone is the natural fit: copy the node's value, then recursively clone each child.
- The key point is that the copy must be deep -- sharing child references would alias the original structure.
- The
Nonebase case returnsNone. - An iterative version uses a stack of
(original, copy)pairs.
💻 Benchmark Python3 Implementation
class Solution:
def cloneTree(self, root: "Optional[Node]") -> "Optional[Node]":
if not root:
return None
node = Node(root.val) # shallow copy of the value
node.children = [self.cloneTree(c) for c in root.children] # deep copy
return node⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is copied once.
💾 Space Complexity
O(h) for the recursion stack, where h is the tree depth.
⚠️ Interview Pitfalls & Follow-ups
- Sharing the children list:
node.children = root.childrenaliases the original; the list and every node in it must be copied. - Using
copy.copy: a shallow copy still shares the children. - Forgetting the empty-tree case:
Nonemust be handled before accessing.val. - Recursing on a very deep tree: the depth can reach 1000, which is within Python's default limit but close.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.