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格式编写，包含代码块、表格、列表等元素，便于技术文档的阅读和理解。可以根据需要调整各部分内容的详细程度。