1490. Clone N-ary Tree
這個題目是樹，題目要考察是否可以寫出遍歷整棵樹的程式碼，類似的題目是 133. Clone Graph 的，但是該題有其他要注意的地方。
廣度優先搜索
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution:
def cloneTree(self, root: 'Node') -> 'Node':
if not root:
return None
head = Node(root.val)
queue = deque([(root, head)])
while queue:
node, clone = queue.popleft()
children = []
for child in node.children:
tmp = Node(child.val)
children.append(tmp)
queue.append((child, tmp))
clone.children = children
return head
深度優先搜索
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution:
def cloneTree(self, root: 'Node') -> 'Node':
if not root:
return root
def dfs(curr, clone):
if not curr:
return None
for child in curr.children:
clone_child = Node(child.val, [])
clone.children.append(dfs(child, clone_child))
return clone
head = Node(root.val)
return dfs(root, head)