小木的算法日记-多叉树的递归/层序遍历

---

🌲 从二叉树到森林：一文彻底搞懂多叉树遍历的艺术

🚀 引言

你好，未来的算法大神！

在数据结构的世界里，“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的，它简洁、优雅，是许多复杂算法的基石。但现实世界的问题往往更加复杂：一个公司的组织架构、一个操作系统的文件目录……这些都不是简单的“一生二”就能描述的。

这时，多叉树（N-ary Tree） 和 森林（Forest） 便登上了舞台。

这篇文章将带你完成一次平滑的认知升级：

1. 理解：从二叉树到多叉树，再到森林，它们之间究竟是什么关系？

2. 掌握：如何将二叉树的遍历思想（DFS 和 BFS）优雅地迁移到多叉树上？

3. 精通：学习层序遍历的三种核心写法，从入门到精通，并理解其背后的设计哲学。

准备好了吗？让我们一起开始这场探索树木深处奥秘的旅程吧！

---

🧐 概念解析：从二叉到多叉，再到森林

在深入遍历之前，我们先花一分钟理清这几个概念的关系。

核心思想：多叉树是二叉树概念的自然延伸，而森林则是多叉树的集合。

1. 二叉树 (Binary Tree)

每个节点最多只有两个子节点，通常称为 left（左子节点）和 right（右子节点）。

      # 二叉树的节点定义
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right

2. 多叉树 (N-ary Tree)

每个节点可以拥有任意数量的子节点。我们通常用一个列表 children 来存储所有子节点。

      # 多叉树的节点定义
class Node:def __init__(self, val=0, children=None):self.val = val# 如果不提供 children，则默认为一个空列表self.children = children if children is not None else []

3. 森林 (Forest)

顾名思义，森林就是多棵树的集合。从结构上看，一片森林可以看作是一个包含了多个多叉树根节点的列表。有趣的是，一棵多叉树本身，也可以被视作一个只有一个成员的特殊森林。

---

🧭 深度优先遍历 (DFS)：递归的思想精髓

DFS 的核心是“一路走到底，再回头”。递归是实现 DFS 最自然的方式。让我们用一个绝妙的比喻来理解它——探索房间与钥匙。

二叉树的探索之旅

想象你进入了一座由房间构成的迷宫，每个房间最多有两扇门，分别由“左钥匙”和“右钥匙”打开。

      # 二叉树的遍历框架
def traverse_binary_tree(root: TreeNode):if root is None:return # 门后是空的，返回#  azioni 前序位置: 刚进入房间，还没开新门print(f"前序：到达房间 {root.val}")traverse_binary_tree(root.left) # 用左钥匙，探索左边的分支#  azioni 中序位置: 从左边分支回来，准备去右边print(f"中序：探索完 {root.val} 的左侧")traverse_binary_tree(root.right) # 用右钥匙，探索右边的分支#  azioni 后序位置: 左右都探索完毕，准备离开这个房间print(f"后序：离开房间 {root.val}")

• 前序位置：刚进入房间，立即执行的操作。

• 中序位置：探索完左边所有房间，准备去右边之前执行的操作。

• 后序位置：左右两边的房间都探索完毕，离开当前房间前执行的操作。

多叉树的探索升级

现在，迷宫升级了！每个房间里不再是固定的两把钥匙，而是一把钥匙串 children，上面挂着通往所有下一级房间的钥匙。

      # N 叉树的遍历框架
def traverse_n_ary_tree(root: Node):if root is None:return # 门后是空的，返回#  azioni 前序位置: 刚进入房间，还没用任何一把钥匙print(f"前序：到达房间 {root.val}")for child in root.children: # 依次使用钥匙串上的每一把钥匙traverse_n_ary_tree(child)#  azioni 后序位置: 所有子房间都探索完毕，准备离开print(f"后序：离开房间 {root.val}")

核心区别：

• 二叉树是固定的 left 和 right，所以有中序位置。

• 多叉树是通过 for 循环遍历所有子节点，因此天然地只有前序和后序位置。前序在循环前，后序在循环后。

---

🗺️ 层序遍历 (BFS)：逐层扫描的广度智慧

BFS 像是在水面投下一颗石子，涟漪从中心一圈一圈地向外扩散。它不深入，而是先扫遍同一层的所有节点。实现 BFS 的利器是队列（Queue）。

下面，我们将通过三种方案，层层递进，彻底掌握多叉树的层序遍历。

方案一：基础版 - 只求遍历，不问出处

这是最纯粹的层序遍历，目标仅仅是按层次顺序访问到每个节点，不关心它在哪一层。

      from collections import dequedef level_order_simple(root: Node):if root is None:returnq = deque([root]) # 初始化队列，放入根节点while q:cur = q.popleft() # 从队列头部取出一个节点# 访问当前节点print(f"访问到节点: {cur.val}")# 将其所有子节点加入队列尾部for child in cur.children:q.append(child)

优点：代码简洁，逻辑清晰。
缺点：无法知道当前节点所在的深度。

方案二：进阶版 - 巧用 size 记录层数

如果我们想在遍历时知道每个节点位于第几层，怎么办？答案是：在每一轮循环中，只处理当前层的所有节点。

      from collections import dequedef level_order_with_depth_v1(root: Node):if root is None:returnq = deque([root])depth = 1 # 根节点视为第 1 层while q:# 关键：在循环开始前，记录当前队列大小，即当前层的节点数level_size = len(q)print(f"--- 开始处理第 {depth} 层，该层有 {level_size} 个节点 ---")for i in range(level_size):cur = q.popleft()print(f"  depth = {depth}, val = {cur.val}")for child in cur.children:q.append(child)# 当前层处理完毕，深度加一depth += 1

图解示例：
假设我们有如下三层树：

      1 (根)/ | \2  3  4/|\5 6 7

遍历过程：

1. 初始: q = [1], depth = 1。

2. 第一次 while: level_size = 1。

   • 处理节点 1，将其子节点 [2, 3, 4] 入队。

   • q 变为 [2, 3, 4]。

   • depth 变为 2。

3. 第二次 while: level_size = 3。

   • 处理节点 2，将其子节点 [5, 6, 7] 入队。

   • 处理节点 3, 4 (无子节点)。

   • q 变为 [5, 6, 7]。

   • depth 变为 3。

4. 第三次 while: level_size = 3。

   • 处理节点 5, 6, 7。

   • q 变为空，循环结束。

这种写法的优势在于：

• 明确分层：for 循环天然地将每一层的节点处理逻辑框在一起。

• 批量处理：便于对每一层进行统计，如计算层和、找到层最大值等。

方案三：终极版 - State 对象，捆绑节点与深度

有时候，我们希望信息能够随着节点在队列中传递，而不是依赖外部变量。这时，我们可以引入一个 State 类。

比喻时间：快递员与行李牌

想象你是一个快递员，在一个树状小区里送货。

• Node：是收件地址（房间）。

• State：是贴在包裹上的“行李牌”，上面清晰地写着 收件地址（Node） 和 楼层号（depth）。

这样，无论包裹传到谁手里，信息都不会丢失。

      from collections import deque# “行李牌”类，捆绑节点和它所在的深度
class State:def __init__(self, node: Node, depth: int):self.node = nodeself.depth = depthdef level_order_with_depth_v2(root: Node):if root is None:returnq = deque([State(root, 1)]) # 把贴好行李牌的根节点包裹放入队列while q:# 取出队列中的第一个包裹current_state = q.popleft()node = current_state.nodedepth = current_state.depth# 查看行李牌信息，并进行处理print(f"depth = {depth}, val = {node.val}")# 为所有子节点制作新的行李牌（深度+1），并放入队列for child in node.children:q.append(State(child, depth + 1))

为什么这种写法很重要？
虽然在这个场景下，方案二看起来更简洁，但 State 模式的思想* 当问题变得更复杂时，比如在著名的 Dijkstra 或 A 算法中，节点需要携带的就不仅仅是深度，可能还有“从起点到此的成本”等更多信息。State 类提供了一个完美的框架来封装这些状态。

---

✨ 总结

恭喜你，坚持看到了最后！现在，让我们快速回顾一下今天学到的核心知识：

1. 从二叉到多叉：多叉树是二叉树的泛化，遍历逻辑从处理固定的 left/right 变成了 for 循环处理 children 列表。

2. DFS (深度优先)：使用递归，代码优雅，有前序和后序两个关键操作位置，适合“一条路走到黑”的场景。

3. BFS (广度优先)：使用队列，逐层扫描，适合寻找最短路径等场景。我们掌握了三种实现方式：

   • 基础版：最简单，但无法获知深度。

   • size 进阶版：巧妙地按层处理，能记录深度，是面试高频写法。

   • State 终极版：将节点与状态（如深度）绑定，扩展性极强，是通向更高级算法的钥匙。

理论是舟，实践是海。现在，打开你的编辑器，用今天学到的知识去 LeetCode 上征服几道多叉树的题目吧！你会发现，世界豁然开朗。

人之道损不足而利有余，天之道损有余而利不足。