Formatted question description: https://leetcode.ca/all/1490.html
1490. Clone N-ary Tree
Level
Medium
Description
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).
Follow up: Can your solution work for the graph problem?
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
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].
Solution
Use recursion to do the cloning. If root is null, then return null. Otherwise, clone a new root from root, and do the cloning for each child of root and assign the cloned children to the new root. Finally, return the new root.
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {
children = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
children = new ArrayList<Node>();
}
public Node(int _val,ArrayList<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public Node cloneTree(Node root) {
if (root == null)
return root;
Node newRoot = new Node(root.val);
List<Node> children = root.children;
for (Node child : children) {
Node newChild = cloneTree(child);
newRoot.children.add(newChild);
}
return newRoot;
}
}