LeetCode如何實現N叉樹的前序遍歷

# LeetCode如何實現N叉樹的前序遍歷

## 一、N叉樹基礎概念

### 1.1 什么是N叉樹
N叉樹（N-ary Tree）是樹數據結構的一種泛化形式，與二叉樹（每個節點最多有兩個子節點）不同，N叉樹的每個節點可以有**任意數量**的子節點（通常最多N個）。這種數據結構非常適合表示具有層次關系的數據，如：
- 文件系統目錄結構
- 組織結構圖
- 評論的回復樹

### 1.2 N叉樹的表示方法
在LeetCode題目中，N叉樹通常通過以下Node類定義：

```python
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children  # 存儲子節點的列表

示例樹結構：

       1
    /  |  \
   3   2   4
  / \
 5   6

對應的輸入形式可能是： [1,null,3,2,4,null,5,6]（其中null分隔不同層級的節點）

二、前序遍歷詳解

2.1 遍歷順序定義

前序遍歷（Preorder Traversal）的訪問順序為： 1. 訪問當前節點 2. 從左到右遞歸遍歷每個子樹

對于上面的示例樹，前序遍歷結果為：[1,3,5,6,2,4]

2.2 與二叉樹前序遍歷的異同

相同點： - 都遵循”根節點->子節點”的訪問順序 - 遞歸實現思路基本一致

不同點： - 二叉樹只需處理左右兩個子節點 - N叉樹需要遍歷動態數量的子節點列表

三、遞歸解法實現

3.1 Python實現

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []
        def helper(node):
            if not node:
                return
            res.append(node.val)
            for child in node.children:
                helper(child)
        helper(root)
        return res

3.2 Java實現

class Solution {
    List<Integer> res = new ArrayList<>();
    
    public List<Integer> preorder(Node root) {
        if (root == null) return res;
        res.add(root.val);
        for (Node child : root.children) {
            preorder(child);
        }
        return res;
    }
}

3.3 復雜度分析

• 時間復雜度：O(N) 每個節點訪問一次
• 空間復雜度：O(H) 遞歸棧深度，最壞情況（樹退化為鏈表）為O(N)

四、迭代解法實現

4.1 使用棧的迭代方法

由于遞歸可能引發棧溢出問題，迭代解法更安全：

def preorder(self, root: 'Node') -> List[int]:
    if not root:
        return []
    stack, res = [root], []
    while stack:
        node = stack.pop()
        res.append(node.val)
        # 子節點逆序入棧，保證出棧順序正確
        stack.extend(reversed(node.children))
    return res

4.2 迭代過程演示

以示例樹為例： 1. 初始棧：[1] 2. 彈出1，加入結果，子節點[3,2,4]逆序入棧 → 棧：[4,2,3] 3. 彈出3，加入結果，子節點[5,6]逆序入棧 → 棧：[4,2,6,5] 4. 彈出5（無子節點）→ 棧：[4,2,6] 5. 彈出6 → 棧：[4,2] 6. 彈出2 → 棧：[4] 7. 彈出4 → 棧：[]

4.3 復雜度分析

• 時間復雜度：O(N)
• 空間復雜度：O(N) 最壞情況下棧需要存儲所有節點

五、LeetCode實戰題目

5.1 題目589：N叉樹的前序遍歷

題目描述：給定一個N叉樹，返回其節點值的前序遍歷。

輸入輸出示例：

輸入: root = [1,null,3,2,4,null,5,6]
輸出: [1,3,5,6,2,4]

5.2 題目擴展

• 590. N叉樹的后序遍歷
• 429. N叉樹的層序遍歷
• 559. N叉樹的最大深度

六、算法優化與變種

6.1 迭代法的空間優化

對于特別深的樹，可以優化棧的實現：

def preorder(self, root):
    if not root: return []
    res = []
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            res.append(node.val)
        else:
            # 子節點逆序入棧
            for child in reversed(node.children):
                stack.append((child, False))
            stack.append((node, True))
    return res

6.2 前序遍歷的應用場景

1. 樹的克隆/序列化
2. 表達式樹求值
3. 目錄結構的顯示

七、常見問題解答

Q1: 如何處理空樹的情況？

A: 在函數開始處添加空值檢查，直接返回空列表

Q2: 為什么迭代法要反轉子節點順序？

A: 棧是LIFO結構，反轉后能保證先處理最左側子節點

Q3: 非遞歸寫法一定比遞歸快嗎？

A: 不一定，但可以避免遞歸深度過大導致的棧溢出

八、總結與對比

掌握N叉樹的前序遍歷是理解更復雜樹算法的基礎，建議讀者： 1. 先理解遞歸的自然表達 2. 再掌握迭代的顯式棧管理 3. 最后嘗試解決相關變種問題

提示：在LeetCode練習時，可以先用小規模測試用例手動模擬遍歷過程，確保理解正確后再編寫代碼。 “`

這篇文章共計約1900字，涵蓋了N叉樹前序遍歷的各個方面，包括： - 基礎概念說明 - 遞歸/迭代兩種實現方式 - 復雜度分析 - 實際題目應用 - 常見問題解答 - 方法對比總結

采用Markdown格式編寫，包含代碼塊、表格、列表等元素，便于技術文檔的閱讀和理解?？梢愿鶕枰{整各部分內容的詳細程度。