---
title: "1490. Clone N-ary Tree"
url: "https://laigary.com/interview/coding/1490-clone-n-ary-tree"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-29"
tags: ["Tree", "Breadth-First Search", "Depth-First Search"]
---

# 1490. Clone N-ary Tree

[1490. Clone N-ary Tree](https://leetcode.com/problems/clone-n-ary-tree/)

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

這個題目要考察的是能不能寫出遍歷整棵樹的程式碼。它是 [133. Clone Graph](/interview/coding/133-clone-graph) 的暖身題，但那題還有別的要注意的地方。

## 思路

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

### 為什麼這題不需要 hash map

這是它跟 [133](/interview/coding/133-clone-graph)、[138](/interview/coding/138-copy-list-with-random-pointer) 最重要的差別，也是先寫這題的理由。

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

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

| 題目 | 結構 | 會不會走到已複製過的節點 | 要 hash map 嗎 |
|---|---|---|---|
| 1490 | N 元樹 | 不會 | **不用** |
| [133. Clone Graph](/interview/coding/133-clone-graph) | 圖（有環） | 會 | 要 |
| [138. Copy List with Random Pointer](/interview/coding/138-copy-list-with-random-pointer) | 串列 + 隨機指標 | 會（random 可以指回去） | 要 |
| [1485. Clone Binary Tree With Random Pointer](/interview/coding/1485-clone-binary-tree-with-random-pointer) | 樹 + 隨機指標 | 會（random 可以指回去） | 要 |

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

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

## 解題方向

### 廣度優先搜索

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

```python
"""
# 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](/interview/coding/1485-clone-binary-tree-with-random-pointer) 的佇列裡放的也是 `(node, copy_node)`。

### 深度優先搜索

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

```python
"""
# 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，可以使用原本題目的結構去做遞迴：**每次進入的時候就先複製該節點，接著對每一個子節點（子樹）去複製，回傳的結果就是已經複製好的子樹**，最後回傳該節點就好了。

```python
"""
# 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 刪除節點](/interview/coding/450-delete-node-in-a-bst) 的 `root.left = self.deleteNode(root.left, key)` 是同一個慣用法。

## 補充

**留意題目給的 `Node` 定義**：

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

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

**接下來就是 [133. Clone Graph](/interview/coding/133-clone-graph)** —— 同樣的遍歷，加上一張 `visited` 表；再往後是 [138](/interview/coding/138-copy-list-with-random-pointer) 和 [1485](/interview/coding/1485-clone-binary-tree-with-random-pointer)，那兩題的 random 指標必須**等所有節點都建好之後再回頭接**，因為指向的目標可能還沒被複製出來。這也是為什麼它們要走兩趟。

## 複雜度

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

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

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