1490. Clone N-ary Tree

──────────────────────────────────────────────────────────────────────

把一棵 N 元樹深拷貝一份 —— 結構和值都一樣，但不能共用任何一個節點。

這個題目要考察的是能不能寫出遍歷整棵樹的程式碼。它是 133. Clone Graph 的暖身題，但那題還有別的要注意的地方。

思路

深拷貝只有兩件事要做：每走到一個節點就 new 一個新的，然後把新節點之間的關係接起來。走訪本身用 BFS 或 DFS 都可以。

為什麼這題不需要 hash map

這是它跟 133、138 最重要的差別，也是先寫這題的理由。

樹沒有環，而且每個節點只有一個父親 —— 所以往下走的時候，你碰到的每個孩子都是「還沒被複製過的新節點」。既然不可能重複遇到，就不需要記錄「這個節點我複製過了嗎、它的複製品是誰」。

一旦結構裡出現「可能指回已經走過的地方」的邊，這個前提就垮了：

題目	結構	會不會走到已複製過的節點	要 hash map 嗎
1490	N 元樹	不會	不用
133. Clone Graph	圖（有環）	會	要
138. Copy List with Random Pointer	串列 + 隨機指標	會（random 可以指回去）	要
1485. Clone Binary Tree With Random Pointer	樹 + 隨機指標	會（random 可以指回去）	要

那個 hash map 的用途永遠是同一個：「原節點 → 複製節點」的對照表。在 133 裡它還兼任 visited，一個字典做兩件事。

想清楚這件事，這一整組題就只剩「要不要那張表」的差別。

解題方向

廣度優先搜索

佇列裡放的是成對的 (原節點, 複製節點) —— 這樣彈出來的時候，才知道要把新建的孩子掛到誰身上。

"""
# 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

「配對入列」是所有 clone 題的 BFS 共同寫法 —— 1485 的佇列裡放的也是 (node, copy_node)。

深度優先搜索

一樣把「原節點」和「複製節點」兩個一起帶著走：

"""
# 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)

不用 helper function

但是這題其實可以不用用到 helper function，可以使用原本題目的結構去做遞迴：每次進入的時候就先複製該節點，接著對每一個子節點（子樹）去複製，回傳的結果就是已經複製好的子樹，最後回傳該節點就好了。

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = 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)

        for child in root.children:
            head.children.append(self.cloneTree(child))
        
        return head

這一版最短，而且它把遞迴的回傳值定義得最乾淨：cloneTree(x) 就是「以 x 為根的那棵子樹的複製品」。 定義成立之後，只要相信遞迴會把子樹處理好，直接 append 就行了。

前面兩版之所以要帶著 clone 走，是因為它們把「建立節點」和「掛上父親」分成兩個地方做；這一版讓孩子自己回傳成品，父親只負責接收 —— 這跟 450 刪除節點的 root.left = self.deleteNode(root.left, key) 是同一個慣用法。

補充

留意題目給的 Node 定義：

self.children = children if children is not None else []

它沒有寫成 def __init__(self, val=None, children=[])，這不是囉嗦 —— Python 的預設參數只會在函式定義時求值一次，寫成 children=[] 的話所有節點會共用同一個 list，加一個孩子全部跟著變。LeetCode 給的模板已經避開了，但自己寫類似結構時要記得。

接下來就是 133. Clone Graph —— 同樣的遍歷，加上一張 visited 表；再往後是 138 和 1485，那兩題的 random 指標必須等所有節點都建好之後再回頭接，因為指向的目標可能還沒被複製出來。這也是為什麼它們要走兩趟。

複雜度

時間 $O (n)$ — 每個節點建立一次、走訪一次
空間 $O (w)$ （BFS，w 是最寬那層的節點數）或 $O (h)$ （DFS，h 是樹高）

其中 $n$ 是節點數，輸出的那棵新樹不計入額外空間 —— 它必然是 $O (n)$ 。

跟 133 對照：那題因為要存 visited，額外空間一定是 $O (n)$ ，省不掉。這題不需要那張表，才是它真正比較簡單的地方。