Problem
Given a root
of an N-ary tree, return a deep copy (clone) of the tree.
Each node in the n-ary tree contains a val (int
) and a list (List[Node]
) of its children.
class Node { public int val; public List<Node> children; }
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Examples
Example 1:
|
|
Example 2:
|
|
Constraints:
- The depth of the n-ary tree is less than or equal to
1000
. - The total number of nodes is between
[0, 10^4]
.
Follow up: Can your solution work for the graph problem?
Solution
Method 1 – Hash Map with DFS (Recursive Cloning)
Intuition
To clone an N-ary tree, we need to create a new node for each original node and recursively clone all its children. To avoid duplicating nodes in case of cycles (though N-ary trees don’t have cycles, but for generality), we use a hash map to keep track of already cloned nodes.
Approach
- Use a hash map to map original nodes to their clones.
- For each node, if it is already cloned, return the clone.
- Otherwise, create a new node with the same value.
- Recursively clone all children and add them to the new node’s children list.
- Return the cloned node.
Code
C++
|
|
Go
|
|
Java
|
|
Kotlin
|
|
Python
|
|
Rust
|
|
TypeScript
|
|
Complexity
- ⏰ Time complexity:
O(N)
, where N is the number of nodes in the tree. Each node is visited once. - 🧺 Space complexity:
O(N)
, for the hash map and recursion stack.