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

  1. A recursive clone is the natural fit: copy the node's value, then recursively clone each child.
  2. The key point is that the copy must be deep -- sharing child references would alias the original structure.
  3. The None base case returns None.
  4. 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.children aliases 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: None must 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems