层序遍历：递归实现

基本概念

层序遍历（Level Order Traversal），又称广度优先遍历（BFS），按照树的层次从上到下、从左到右依次访问结点。

• 通常使用队列实现迭代版。
• 递归实现相对不直观，但可以通过传递当前结点所在的层级（深度），将结点值按层存储到结果列表中。
• 递归版的核心思想：深度优先（DFS）的遍历顺序 + 按层收集。

算法步骤

1. 定义递归函数 dfs(node, level)：
   • 若当前结点为空，直接返回。
   • 若 level 等于结果列表 res 的长度，说明这是该层第一个被访问的结点，需要新增一个空列表。
   • 将当前结点值加入 res[level]。
   • 递归处理左子树，层级加 1。
   • 递归处理右子树，层级加 1。
2. 从根结点（level=0）开始调用 dfs。
3. 返回 res，即按层存储的二维列表。

费曼理解

想象你有一棵家族树，你想按辈分（层）列出所有人。你可以从老祖宗开始，每遇到一个人，就把他加入当前辈分的名单，然后继续找他的孩子们（下一辈）。即使你是按深度优先的方式（一条道走到黑）去拜访，只要记得每个人是第几辈，就能把大家正确放进对应的辈分名单里。

内部实现

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    res = []
    
    def dfs(node: Optional[TreeNode], level: int):
        if not node:
            return
        # 如果当前层还没有列表，则新建一个
        if level == len(res):
            res.append([])
        res[level].append(node.val)
        # 递归处理左右子树，层级+1
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    
    dfs(root, 0)
    return res

复杂度分析

版本	时间复杂度	空间复杂度	说明
递归实现	O(n)	O(n)	每个结点访问一次；空间来自递归栈（最坏 O(n)）和结果存储（O(n)）
迭代（队列）	O(n)	O(n)	每个结点入队出队一次；队列最大宽度 O(n)

• 时间复杂度：每个结点恰好访问一次，O(n)。

• 空间复杂度：

  • 递归栈深度等于树高，最坏 O(n)（斜树）。

  • 结果列表存储所有结点值，O(n)。

  • 因此整体 O(n)。

应用场景

• 按层输出二叉树（如 LeetCode 102 题）。
• 寻找树的最小深度：BFS 按层遍历时，第一个叶子结点所在的层即为最小深度。
• 判断完全二叉树：层序遍历过程中，遇到第一个空结点后，后面应全为空。
• 二叉树的右视图：每层最后一个结点。
• 填充每个结点的下一个右侧结点指针：利用层序遍历连接同一层结点。
• 真实系统：
  • 文件系统目录的图形化展示（如资源管理器按层级展开）。
  • 网络爬虫的广度优先爬取策略。
  • 社交网络的好友推荐（按距离分层）。
  • 打印多行文本的树形结构（如命令行 tree 的输出格式）。

相关

• 102.二叉树的层序遍历