PYTHON LESSON 093
六级易错点排雷大会
逐个识别六级最高发的 5 类错误：递归无出口、二维列表假拷贝、入队不标记、下标起点混乱、遍历张冠李戴。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- [[False]*cols for _ in range(rows)] 各行独立
- 入队瞬间立刻标记 visited/dist
- 完全二叉树门牌号必须从 1 开始
01 · 核心概念
五大高频错误：错例、错因与正确写法
五大高频错误：错例、错因与正确写法：错例：遍历函数拿到 node 就直接访问 node.left，不写空节点判断。报错：AttributeError: 'NoneType' object has no attribute 'left'，严重时 RecursionError。正确写法：函数第一行先写 if node is None: return，先刹车，后干活。
GESP Python 6 级 · 树的遍历GESP Python 6 级 · 宽度优先搜索 BFSGESP Python 6 级 · 完全二叉树流程图是算法的表示方法，不是 Python 语法。
02 · 语法与规则
先记住这 3 条，再开始写程序
[[False]*cols for _ in range(rows)] 各行独立先准确读出这条写法的结构与作用。
入队瞬间立刻标记 visited/dist换一组最小数据，手工推演一次结果。
完全二叉树门牌号必须从 1 开始再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 易错辨析实战：二维 visited 数组的“假拷贝”陷阱
rows, cols = 3, 4
# 错例：[[False] * cols] * rows 看起来造了 3 行，其实 3 行是同一个列表
bad = [[False] * cols] * rows
bad[0][0] = True
print("错误写法 [[False] * cols] * rows：")
for row in bad:
print(row)
print("只标记了 (0,0)，却“传染”了每一行！")
print()
# 正确写法：用列表推导式，每行都是独立的新列表
good = [[False] * cols for _ in range(rows)]
good[0][0] = True
print("正确写法 [[False] * cols for _ in range(rows)]：")
for row in good:
print(row)
print("只有 (0,0) 被标记，各行互不干扰。")错误写法 [[False] * cols] * rows： [True, False, False, False] [True, False, False, False] [True, False, False, False] 只标记了 (0,0)，却“传染”了每一行！ 正确写法 [[False] * cols for _ in range(rows)]： [True, False, False, False] [False, False, False, False] [False, False, False, False] 只有 (0,0) 被标记，各行互不干扰。
“传染”是因为乘号复制的是引用：3 行共用同一个列表对象；推导式每轮新建一行，才能各行独立。
04 · 逐步理解
每一步只解决一个问题
- 01
雷区一：递归忘写出口
错例：遍历函数拿到 node 就直接访问 node.left，不写空节点判断。报错：AttributeError: 'NoneType' object has no attribute 'left'，严重时 RecursionError。正确写法：函数第一行先写 if node is None: return，先刹车，后干活。
def preorder(node): if node is None: # 先写出口！ return - 02
雷区二：二维列表“假拷贝”
错例：visited = [[False]*cols]*rows，标记 (0,0) 后每一行的第 0 列全变 True——乘号复制的是“引用”，3 行其实是同一个列表。正确写法：[[False]*cols for _ in range(rows)]，每行独立。本课 demo 把两种写法并排跑给你看。
visited = [[False] * cols for _ in range(rows)] - 03
雷区三：BFS 出队才标记
错例：格子出队时才写 dist，结果同一个格子被好几个邻居重复入队，步数被反复覆盖、队列越来越长。正确写法：发现新格子、准备入队的那一刻就立刻写 dist/visited——入队即标记。
dist[nr][nc] = dist[r][c] + 1 # 入队前先标记 queue.append((nr, nc)) - 04
雷区四：门牌号从 0 开始
错例：完全二叉树用 0 号位当根，结果“父 k//2、左 2k、右 2k+1”全部错位。正确写法：0 号位空着，根住 1 号，公式才成立。自检口诀：根的爸爸是 0 号空地，while k >= 1 正好停住。
tree = [""] + nodes # 0 号位空着，根住 1 号 - 05
雷区五：遍历方式张冠李戴
错例：题目要“按辈分层序输出家谱”，却写了中序递归，顺序完全不对。正确写法：先想清顺序特征再选工具——按“层/辈分”用队列 BFS；“左-根-右”才是中序。二叉排序树中序得升序这条性质，还能反过来当检查器。
- 06
建立你的排雷清单
把这五条抄进错题本，每道树/搜索题交卷前对照一遍：递归有出口吗？二维数组各行独立吗？入队即标记了吗？门牌号从 1 开始吗？遍历方式选对了吗？五问全过，再点提交。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，观察“传染”现象与正确结果
- 2默写二维列表的正确创建语句
- 3给 BFS 骨架标出“标记”所在的那一行
- 4用自己的话讲清中序与层序的区别
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
完成检查