树、BST 与 Trie · HTML
数学 / 逻辑形态
queue 初始含 root。while queue：level_size=len(queue)；重复 level_size 次 pop 节点并 push children；该批节点深度相同，批结束深度加一。
识别信号
- 输出按深度分组。
- 需要每层和、最大值、最后节点或锯齿顺序。
- 目标是遇到第一个满足条件的最浅节点。
- 父节点产生下一层子节点。
- 递归深度可能过大且偏好迭代。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 子树信息向父聚合 | 高度、平衡性、直径等需 postorder，层序不自然。 |
| 有权边最短距离 | FIFO 只保证相同边数层；非等权需 Dijkstra。 |
| 一般图但不去重 | 树无环且每节点单父；图 BFS 必须在 enqueue 时 visited。 |
核心不变量
每轮开始时 queue 恰包含当前深度的所有节点且不含其他深度；处理固定 level_size 后，queue 恰为下一深度节点。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | FIFO queue、当前深度，以及本层临时 accumulator。 |
| Transition | 弹出本层节点，更新层统计，并按稳定顺序将非空 child 加到队尾。 |
| Frontier / order | 队列中尚未处理的当前层加其后已发现下一层；level_size 是两层边界快照。 |
Python 骨架
from collections import deque
def levels(root):
if root is None: return []
queue, out = deque([root]), []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
out.append(level)
return out
正确性思路
- 初始队列只含深度 0 根，基例成立。
- 一轮只弹出快照中的 level_size 个节点，它们由不变量具有相同深度。
- 它们的所有非空 child 恰是下一层且每个有唯一父，批结束恢复不变量。
复杂度
| Time | Space | Parameters |
|---|
| O(n) | O(w)，w 为最大层宽 | n 为节点数，w 为任一层最大节点数。 |
边界条件
- 空树
- 单节点
- 极宽树
- 最小深度必须在真实叶子退出
- 锯齿输出只反转展示不改 enqueue
- 多叉树 child 顺序
错误模式
| Pattern | Why it fails / fix |
|---|
| for range(len(queue)) 动态重算 | 必须在本轮开始冻结长度，否则会把下一层也处理进来。 |
| 最小深度遇到单空 child 就返回 | 叶子要求所有 child 都为空，不是缺任意一侧。 |
| 为锯齿反转 enqueue 顺序 | 可能破坏下一层结构；保留遍历顺序，只反转层结果或双端写入。 |
| 用 list.pop(0) | Python 列表头删 O(n)；使用 deque.popleft()。 |
选择与排除规则
- 需求出现‘每层/最浅/右视图’时优先层序。
- 每轮先保存 level_size。
- 早退条件在 pop 后对已确定层级节点检查。
- 图版本在 enqueue 时标 visited。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 层输出 [[8],[3,10],[1]]，最大队列宽为 2。 |
| Setup | 根 8 的孩子为 3、10，节点 3 还有孩子 1。 |
| Trace | 轮次队列分别为 [8]、[3,10]、[1]。 |
Recall prompts
我的补充