专题进阶 · 树与范围查询推荐总顺序 · 第 48 / 148 课

用队列长度冻结当前层,避免把下一层混入本层结果。

先学会这些,再进入本课 二叉树 广度优先搜索 队列
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

层序遍历Level Order

借助队列逐层访问,记录每轮队列长度可区分层。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用队列长度冻结当前层,避免把下一层混入本层结果。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

按层返回树 4(2(1,3),7):[[4],[2,7],[1,3]],怎样知道一层何时结束?

02一步步得到方法

队列同时容纳当前层与下一层

开始时只有根。处理当前层的每个节点时,把孩子放到队尾;先进先出保证这些孩子在当前层剩余节点之后处理。

每层开始先保存 size=len(queue)。接下来恰好弹出 size 个节点,其间新增的孩子不属于当前层。若循环条件直接跟随不断增长的队列长度,层边界会被打乱。

树与一般图的区别

真正的树中每个节点只有唯一父节点,沿孩子访问不会重复,通常不需要 visited。若输入是带共享子节点或回边的图,必须加入判重并重新说明最短层数的含义。

层号从 0 开始时等于距根的边数;若题目把根定义为第 1 层,则显示编号加 1,算法不变。

一层的边界在扩展前固定

BFS 队列中先是当前层剩余节点,后是新加入的下一层节点。进入某一层时记录队列长度,恰好弹出这么多个,便能把层分开输出。

若循环条件不停读取变化后的队列长度,新压入的孩子可能被算进同一层。固定层大小不是为了访问到节点,而是为了保留正确的距离分组。

03把一个小例子完全算清楚

树 4(2(1,3),7)。

步骤计算与状态为什么这样做
层 0,size=1弹 4,入 2、7输出 [4]
层 1,size=2弹 2、7,入 1、3输出 [2,7]
层 2,size=2弹 1、3,无孩子输出 [1,3]

窄屏可左右滑动表格,阅读完整计算与理由。

每轮开始队列恰好包含当前层的全部节点。

04为什么这个方法成立

  1. 根单独构成第 0 层。
  2. 若队列当前为第 d 层,依次取出它们并加入孩子,得到且仅得到第 d+1 层。
  3. 固定 size 使本轮不会越过层边界,归纳得到完整分层结果。

05把推导翻译成代码

Python · 可独立运行的教学实现

from collections import deque
def levels(tree):
    if tree is None:
        return []
    queue, result = deque([tree]), []
    while queue:
        row = []
        size = len(queue)
        for _ in range(size):
            value, left, right = queue.popleft()
            row.append(value)
            if left is not None:
                queue.append(left)
            if right is not None:
                queue.append(right)
        result.append(row)
    return result

逐个理解关键决定

size = len(queue)
在本层开始冻结数量;不要每弹一个节点就重新定义层大小。
queue.popleft()
用双端队列保持 O(1) 头部移除。

06时间、空间与实现范围

时间 O(n),工作队列 O(w),w 是最大层宽;答案空间 O(n)。

平衡树最后一层可能有约一半节点,所以 BFS 空间未必小于 DFS 的 O(h)。

07改变条件,检查哪里会出错

将层序和中序混淆

层序按距离,中序按左根右;二者不存在一般相同的输出顺序。

把树上的无需 visited 直接用于一般图

一般图可能有环或多个父路径,BFS 需要标记已发现节点,防止重复入队。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

树高 3,就说明队列最多 3 个节点吗?

需要一点提示

高度与宽度不同。

查看解析与答案

不说明。满二叉树第三层有 4 个节点,更高时宽度可指数增长。

练习 2 · 边界与辨析

怎样求每层平均值?

需要一点提示

已有 row。

查看解析与答案

对每层求 sum(row)/len(row),注意数值范围与浮点精度。

练习 3 · 变式与迁移

怎样找最小深度?

需要一点提示

第一个叶子在哪一层?

查看解析与答案

层序首次遇到无孩子节点时即可返回其层数,因为更浅层已全部检查。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。