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为什么这个方法成立
- 根单独构成第 0 层。
- 若队列当前为第 d 层,依次取出它们并加入孩子,得到且仅得到第 d+1 层。
- 固定 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
树高 3,就说明队列最多 3 个节点吗?
需要一点提示
高度与宽度不同。
查看解析与答案
不说明。满二叉树第三层有 4 个节点,更高时宽度可指数增长。
怎样求每层平均值?
需要一点提示
已有 row。
查看解析与答案
对每层求 sum(row)/len(row),注意数值范围与浮点精度。
怎样找最小深度?
需要一点提示
第一个叶子在哪一层?
查看解析与答案
层序首次遇到无孩子节点时即可返回其层数,因为更浅层已全部检查。