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 children; } Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
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, 104].
- code
class Solution:
def cloneTree(self, root: 'Node') -> 'Node':
map = {}
if not root: return root
map[root] = Node(root.val)
level = [root]
while level:
for node in level:
for child in node.children:
map[child] = Node(child.val)
map[node].children.append(map[child])
level = [i for node in level for i in node.children if i]
return map[root]
- code
class Solution:
def cloneTree(self, root: 'Node') -> 'Node':
if not root: return root
new_root = Node(root.val)
stack = [(root, new_root)]
while stack:
old_node, new_node = stack.pop()
for child_node in old_node.children:
new_child_node = Node(child_node.val)
new_node.children.append(new_child_node)
stack.append((child_node, new_child_node))
return new_root