代码随想录训练营打到第13天正好是一个分水岭。前12天我们处理的是数组、链表、哈希表、字符串这些“线性结构”Day13一上来就把二叉树摆到面前。这一天我记忆特别深因为从它开始刷题不再是单纯地找位置、移动双指针而是要学会用两种视角看问题一种是层序展开的BFS一种是递归展开的DFS。这一天的题单安排的是层序遍历、翻转二叉树、对称二叉树看起来都不难但实际写起来坑不少。这篇我就聊聊这一天的完整复盘包括题单设计逻辑、核心原理、可复现代码以及我踩过的那些坑。如果你正准备开始刷二叉树或者正在训练营Day13附近这篇应该能帮你少走弯路。1. 内容整体设计与思路拆解1.1 从线性到树训练营为什么把二叉树安排在Day13代码随想录的课程节奏是有讲究的。前12天从数组二分查找开始一路打过链表、哈希表、字符串、双指针、栈和队列本质上都是在处理“线性关系”一个元素只有一个前驱和一个后继。这样的结构用循环、指针、栈都能很好操作。但到了二叉树元素出现了“左右分支”一个节点最多有两个后继递归就成了最顺手的工具。Day13这个位置很关键因为前面已经讲过函数的调用栈也讲过栈和队列的应用这两块沉淀下来正好支撑二叉树的两种基础遍历递归DFS和队列BFS。训练营把Day13的主题定为二叉树入门但并没有一上来就讲前中后序遍历的三部曲而是先用层序遍历打开BFS的思维方式用翻转和对称引出递归的返回值设计。这个设计背后藏着一条主线先会用“层”的视角看树再用“递归镜像”的视角理解树的对称性。我在Day13最大的感受是这些题目单独拎出来每道都不难但组合在一起会让你突然意识到递归函数返回值的意义——不只是返回结果还承担着“把子问题的解组装成父问题解”的任务。后面的路径总和、最近公共祖先、回溯剪枝全都跑不掉这套逻辑。1.2 Day13的题单拼图不同期数的训练营可能在细节上有差别但我这一期Day13核心就是下面这几题题目核心考点对应技巧102 二叉树的层序遍历BFS层序模板队列 每层size快照103 锯齿形层序遍历层序的边界变化判断当前层是否需要逆序429 N叉树的层序遍历一题多解通用层序模板孩子列表遍历226 翻转二叉树递归交换子树前序/后序/层序均可101 对称二叉树递归镜像判断左右子树同时遍历剪枝返回题目不多但每一道都卡住过一批人。层序遍历看起来就是队列进出真写起来有人会把每层边界搞错翻转二叉树有人会用中序遍历结果交换完的树莫名其妙不完整对称二叉树更不用说了递归参数怎么对应都是个坎。把这些题在一天内集中刷完收获不只是AC而是把“树的遍历”这件事吃透。1.3 为什么这一天值得反复咀嚼很多同学刷到Day13会觉得“太简单了都是套路”。但我想说这一天是整个二叉树章节的地基。层序遍历的size快照技巧后面在求树的最大宽度、二叉树的右视图、填充next指针时都会用到递归翻转时的swap顺序直接影响前序、中序、后序的选择对称二叉树的判断逻辑和后续回溯算法的“剪枝”一脉相承——一旦某个条件不满足立刻返回false不再递归下去。这一天的每一个细节都不是孤立的。我二刷的时候重新写了一遍这五题发现每道题都能用至少两种方法写出来。层序遍历不仅能用队列BFS还能用递归DFS记录深度翻转二叉树不仅能用递归还能用栈模拟。这才意识到训练营的意图不是让你背模板而是让你在多种实现中体会“遍历顺序”和“递归边界”的本质。2. 核心细节解析与实操要点2.1 层序遍历的队列快照一个细节决定成败先看一个最常见的错误写法from collections import deque def levelOrder(root): if not root: return [] res [] q deque([root]) while q: row [] # 错误每次循环都重新取 q 的长度 for _ in range(len(q)): node q.popleft() row.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(row) return res这个写法在大多数测试用例下居然能过但碰上左右子树高度不一致的树就会出问题。原因是len(q)在for循环里会随着popleft和append不断变化循环次数完全不可控。正确做法是在进入循环前先抓拍当前层节点数while q: size len(q) row [] for _ in range(size): node q.popleft() row.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(row)size就是这一层开始前的队列长度也是一个快照。这样后面就算往队列里塞进下一层的所有节点这一轮也只处理size个。理解这个细节不只是为了AC后面处理二叉树的锯齿形遍历奇数层反转、N叉树层序、二叉树最大宽度都是同一套逻辑。时间复杂度每个节点入队出队一次O(n)空间复杂度是队列中最多的一层节点数最坏情况是完美二叉树的最后一层O(n/2)也就是O(n)。2.2 翻转二叉树的三种顺序与中序陷阱翻转二叉树最直观的思路是递归交换左右孩子def invertTree(root): if not root: return None root.left, root.right root.right, root.left invertTree(root.left) invertTree(root.right) return root这是典型的前序遍历先交换当前节点的左右孩子再递归处理左子树最后处理右子树。前序和后序都没有问题层序也可以用队列逐层交换。真正有坑的是中序遍历# 错误示例 def invertTree_wrong(root): if not root: return None invertTree_wrong(root.left) # 处理左子树 root.left, root.right root.right, root.left # 交换 invertTree_wrong(root.right) # 处理“右子树”这段代码逻辑上很像中序但实际跑起来会发现有些节点没交换有些节点被交换了两次。原因在于交换左右孩子之后原来的右子树已经被换到了左边而原来的左子树跑到了右边下面一行处理的“右子树”实际上是已经被处理过一次的原来的左子树而真正的右子树在原左子树位置永远不会被访问到。我给个直观类比你左手拿着苹果右手拿着梨中序翻转是先把左手里的苹果削好递归处理左子树再把苹果和梨对调然后去削现在右手的“苹果”。这个苹果其实已经被削过了而原来的梨已经被换到左手但你的后续逻辑只处理右手梨就被漏掉了。所以翻转二叉树推荐前序或后序别用中序踩泥坑。2.3 对称二叉树镜像映射的递归判断对称二叉树不是简单比较左右子树的值而是比较整棵树的左右镜像。递归函数需要同时传入两个对应节点def isSymmetric(root): def compare(left, right): if left is None and right is None: return True if left is None or right is None: return False if left.val ! right.val: return False return compare(left.left, right.right) and compare(left.right, right.left) return compare(root.left, root.right)这里最绕的是递归参数映射左子树的左孩子要和右子树的右孩子比较左子树的右孩子要和右子树的左孩子比较。因为对称的本质是左右交替映射。这个函数还体现了一个重要概念——剪枝。三个if判断都放在递归之前一旦发现左右有一个为空或值不同立刻返回false不再继续展开子树。这种“提前终止递归”的思路就是回溯算法里剪枝的雏形。Day13先通过对称二叉树让你感受剪枝后面做八皇后、组合总和的时候你会发现其实是一模一样的逻辑。3. 实操过程与核心环节实现3.1 环境与调试准备刷二叉树题我不建议直接在线编译一遍就跑建议准备一个本地调试环境。我用的是VS Code Python写一个专门的文件夹放二叉树题每道题写完之后额外加一个辅助函数tree_to_list把树转成层序列表方便肉眼核对。调试树的常见痛点是可视性差给你一棵树你根本不知道递归过程发生了什么。我的经验是在递归函数里加打印输出当前节点值、左右孩子值以及返回值。这样能很快定位边界问题。但LeetCode提交前记得删掉print否则影响性能。3.2 三道核心题的完整代码对照Day13的层序模板我最后整理成了固定写法每天先默写三遍from collections import deque def level_order(root): if not root: return [] res [] q deque([root]) while q: size len(q) level [] for _ in range(size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res翻转二叉树我习惯用后序写因为更贴合“由下往上交换”的思路def invert_tree(root): if not root: return None left invert_tree(root.left) right invert_tree(root.right) root.left right root.right left return root对称二叉树的递归实现已经在上文给出。这里再补一个迭代版本用双端队列逻辑上和递归一样但没有函数调用栈的风险from collections import deque def is_symmetric(root): if not root: return True q deque([root.left, root.right]) while q: left q.popleft() right q.popleft() if left is None and right is None: continue if left is None or right is None: return False if left.val ! right.val: return False q.append(left.left) q.append(right.right) q.append(left.right) q.append(right.left) return True注意迭代版本里左右节点成对入队也是按照“左左对右右、左右对右左”的顺序这个顺序如果搞反判断结果就不对称了。3.3 现场执行与输出验证我以一棵简单二叉树为例1 / \ 2 2 / \ / \ 3 4 4 3层序遍历输出应为[[1], [2,2], [3,4,4,3]]对称判断应返回true。我在调试时会在每个节点入队前打印当前队列状态检查有没有多余的空节点入队。很多人写迭代对称时会顺手把空节点也塞进队列导致循环无法终止这是常见bug。我的解决方法是空节点不直接入队而是每次取两个节点后判断是否为空如果一方为空另一方不为空立即返回false。3.4 复杂度分析怎么写在纸上面试时除了写出代码还要能说明复杂度。层序遍历的复杂度很好理解每个节点访问一次时间O(n)空间上队列中最多存放一整层节点最坏O(n)。翻转二叉树使用递归递归深度是树的高度平均O(log n)最差链表状树是O(n)所以空间复杂度O(n)时间O(n)。对称二叉树同理。这三题的时间复杂度都是O(n)但空间要区分递归栈和队列。这个细节面试官大概率追问提前想清楚。4. 常见问题与排查技巧实录4.1 递归栈溢出尤其是单链表树二叉树在极端情况下会退化成一条链比如每个节点只有左孩子。这时递归翻转二叉树递归深度就是节点数如果节点数上万Python默认递归深度只有1000直接报RecursionError。遇到这种情况要改用迭代思路。翻转二叉树可以用栈模拟def invert_tree_iterative(root): if not root: return None stack [root] while stack: node stack.pop() node.left, node.right node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root层序遍历本身就是迭代的不会栈溢出。对称二叉树的迭代双端队列版本也同样安全。所以当面试官问“如果树特别深会怎样”不要傻乎乎说递归很好要主动切换到迭代实现。4.2 空指针和空节点的边界卡点层序遍历里最常见的报错是NoneType has no attribute left。原因是在入队前没有判断孩子是否存在。我一般遵守一个原则只有非空节点才入队。这样队列里不会出现None取出来直接访问val和左右孩子都没问题。但对称二叉树的迭代版本里我反而需要同时处理空节点来判断结构所以用的人是左右节点成对取出的方式。翻转二叉树最容易漏掉根节点为空的情况if not root: return None这个边界不写LeetCode会直接报错。另外交换左右孩子时如果孩子是空节点交换本身没问题但后续递归前需要判空。4.3 递归函数返回值与签名错乱对称二叉树的老问题是有人在compare函数里忘记返回falsedef compare(left, right): if not left and not right: return True if not left or not right: return False if left.val ! right.val: return False if left.val right.val: return compare(...) # 忘记写return有些同学觉得最后一句是“最后一个操作”可以不用return但Python里函数没有显式return时默认返回None而外层的isSymmetric又把这个None当成真值用结果出现“有时对有时错”的诡异现象。排查办法很简单在所有需要返回布尔值的递归函数里把return写全可以用断言或者类型检查提醒自己。4.4 刷题复盘小工具Day13开始题目会越来越复杂我建议自己做一张Excel表格列名包括日期、题目、考察点、我的第一思路、最佳思路、复杂度、错误点、二刷状态。比如Day13的五道题记录错误点后你会发现自己最怕的是“递归返回值缺失”和“层序size没用快照”。二刷的时候直接看表格不用重新整个刷一遍效率高很多。这也是代码随想录训练营强调的“温故而知新”落到实处。4.5 一个容易被忽略的语言细节Python的deque和普通list都可以模拟队列但用list的pop(0)是O(n)操作刷题时树节点规模一大就超时。所以层序遍历一定要用collections.deque的popleft()时间复杂度O(1)。如果用C则是queuepushpop的标准搭配用Java建议LinkedList实现队列避免ArrayList的remove(0)高开销。这个细节虽然小但在面试手写代码时能体现你对底层数据结构的熟悉程度。5. 结尾一点真实的复盘体会我在Day13卡得最久的不是层序而是对称二叉树。当时总觉得用中序遍历拿到序列再比较序列是否回文就能判断对称结果很多子树不对称却中序序列相同。后来才明白对称的判定必须同时比较结构和值任何试图“序列化后比较”的做法在一般二叉树上都不可靠。这个教训让我在后面的算法题里养成了一个习惯先想清楚“需要比较什么东西”再去写递归函数参数而不是先写代码再猜。最后分享一个小技巧Day13的这几道题我建议你尝试用“完全理解后默写”的模式来刷先看一遍题解睡觉前不看代码手动写一遍再和第2节里的模板对照。用不了三天层序遍历和对称判断的这些结构就会刻进脑子里。到Day14开始迭代遍历二叉树时你会发现今天的递归思维和队列技巧全都是地基省下的时间足够再刷一组回溯剪枝的题目了。