代码随想录训练营到了第12天二叉树开始上强度了。今天的四道题——翻转二叉树、对称二叉树、二叉树的最大深度、最小深度表面上是四道独立题目实际全是“遍历框架”的变体。如果你像我一样前几天的“二叉树的遍历”已经练到闭眼能写递归今天应该只花一个多小时如果递归还没吃透这一天刚好给你一个集中突破的机会。这篇复盘文章我把递归三部曲、层序模板、还有当天踩过的坑全整理出来希望能帮后面打卡的同学少走弯路。1. 为什么这几道题值得单独练一天训练营把226、101、104、111这四道题放在同一天不是随机拼凑。它们都有一个共同特征不要求你发明新遍历方式而是把已经学过的递归遍历和层序遍历套到不同的业务逻辑上。换句话说前几天的题目考查“能不能写出遍历”从这天开始考查“能不能用好遍历”。1.1 四道题其实都是遍历的变形把四道题摊开看本质非常统一226.翻转二叉树遍历到任意一个节点时交换它的左右孩子。用前序、后序、层序都可以目的只是“访问到每一个节点然后做一次交换”。101.对称二叉树不是单独遍历一棵树而是同时遍历左右两棵子树比较它们是否互为镜像。这是遍历框架的升级版——之前是单指针走一棵树这次是双指针同时走两棵树。104.二叉树的最大深度遍历过程中记录当前节点的深度到叶子节点时更新答案。递归解法里用的是后序遍历因为要先把左右子树的深度算出来才能推出当前节点的深度。111.二叉树的最小深度逻辑上和最大深度对称但它有一个特别容易踩的坑“最小”不能简单用min套因为只有叶子节点才配作为终点。当你意识到这四道题都在“遍历”这个地基上变形就不需要再背额外的东西只需要把递归三部曲和层序框架吃透。1.2 递归三部曲当天真正的主角刷二叉树的递归题我一直觉得有一套万能心法代码随想录里管它叫“递归三部曲”我自己用下来确实能覆盖90%的树问题确定参数和返回值这个递归函数要传什么进去最后要向调用方返回什么。确定终止条件什么时候该直接返回不再向下递归。确定单层递归逻辑当前这一层节点该做什么事然后如何调用下一层。听起来抽象其实很像公司里的任务派发。管理层当前节点不需要自己干完整棵树只需要处理自己这一层的事情然后把左半、右半的任务分别交给两个下级下级再往下派。每个层级只关心自己的局部动作组合起来就是整棵树的答案。对应到代码上二叉树的递归题大多长这样def traversal(root): if not root: # 终止条件空节点直接返回 return 0 # 单层递归逻辑处理当前节点 left_val traversal(root.left) right_val traversal(root.right) # 利用左右子树的结果推出当前结果 return something_based_on(left_val, right_val)遇到一道新题先问自己三个问题这个函数返回什么终止条件是什么当前节点要做什么答案理清了递归题基本能写对一大半。1.3 层序遍历框架另一条捷径递归能解决的题层序遍历大多数也能解决而且今天有几道题用层序反而更容易理解。层序遍历的标准框架是用队列按层推进核心是每次进入新的一层时先记录当前队列长度再一次性处理完这一层from collections import deque def level_order(root): result [] if not root: return result q deque([root]) while q: level_size len(q) # 当前层的节点数 level [] for _ in range(level_size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level) return result其中level_size len(q)这步特别关键。因为队列在出队入队的过程中长度一直在变如果不提前固定当天这一层的节点数就会把下一层的节点混进同一层处理导致分界线丢失。这个框架记熟之后翻转二叉树、求深度、求层数都能从它上面做很小的改造成型。2. 226.翻转二叉树前序遍历的直观应用翻转二叉树这题看完题目描述就知道要做什么把每个节点的左右孩子全部交换。比如样例里根节点是4左孩子2右孩子7翻转后变成左孩子7、右孩子2然后每个子树也要继续翻转。很多人第一反应是“死记代码”但我建议先想清楚一个问题交换操作应该发生在什么时候2.1 题目的本质是什么翻转一棵二叉树等价于对每个节点执行swap(root.left, root.right)并且这个操作要覆盖整棵树的所有节点。既然我们已经有前序、中序、后序、层序遍历这些武器最自然的方式就是选一种遍历方式在“访问节点”时执行交换。理论上先序和后序都能得到正确结果因为交换操作只依赖当前节点本身不依赖它的孩子是否已经被交换过。而中序遍历则会出错这一点是当天很多同学都掉进去的坑。2.2 递归解法前序位置交换直接用前序遍历的模板先交换当前节点的左右孩子再递归处理左右子树class Solution: def invertTree(self, root): if not root: return None root.left, root.right root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root这段代码的终止条件是not root空节点直接返回。单层逻辑是交换、递归左、递归右。如果你把交换语句放到两个递归调用之后就是后序遍历版本class Solution: def invertTree(self, root): if not root: return None self.invertTree(root.left) self.invertTree(root.right) root.left, root.right root.right, root.left return root为什么后序也行因为每个节点都会被访问一次交换这个操作只要发生在“处理当前节点”那一步就行它不依赖左右孩子的交换结果。前序和后序的区别只是“先交换再递归”还是“先递归再交换”最终效果等价。2.3 中序遍历翻转的坑如果把交换放在两个递归调用之间写成中序逻辑# 错误示范 self.invertTree(root.left) root.left, root.right root.right, root.left self.invertTree(root.right)假设根节点是AA的左孩子是B右孩子是C。执行顺序是这样的先递归翻转A的左子树B交换A的左右孩子此时A.left变成了CA.right变成了B再递归翻转A.right而这时A.right是原来的BB会被再翻一次。结果是原来的右子树C完全没被访问而左子树B被翻转了两次。翻转两次等于没翻所以最终结果一眼看上去就是错的。即使你运气好输了一棵特殊形状的树碰巧对了也是偶然不是可靠的解法。这个教训让我记住一句话只要操作放在“遍历到某个节点”的时机里就必须保证操作位置不影响后续遍历范围。中序之所以不行是因为交换操作改变了右子树的位置而后面的递归还在用“root.right”这个引用结果就自相矛盾了。2.4 层序解法代码最直观如果觉得递归的交换时机容易绕层序遍历可以完全避免这个问题。因为层序是“一层一层扫”每个节点出队时直接交换左右孩子然后把这个节点的左右孩子入队不需要担心递归调用顺序from collections import deque class Solution: def invertTree(self, root): if not root: return None q deque([root]) while q: node q.popleft() node.left, node.right node.right, node.left if node.left: q.append(node.left) if node.right: q.append(node.right) return root层序解法的时间复杂度是O(N)空间复杂度最坏O(N)当树接近满二叉树时队列里会同时存储最后一层所有节点。从刷题角度看递归版代码最短层序版最好理解两种我建议都写一遍。3. 101.对称二叉树镜像比较的后序遍历对称二叉树这道题我第一次看的时候想反了以为只要比较根节点的左右孩子值是否相等就行。实际上要比较的是整棵子树的结构和值是否互为镜像。3.1 为什么不能直接比较左右子树是否相等打个比方对称的人照镜子镜子里的人举起的是右手我举起的是左手。要判断两人是不是对称不能拿“我的左手”去对比“镜子里人的左手”而是拿“我的左手”去对比“镜子里人的右手”。对应到二叉树根节点左子树的左孩子应该对比右子树的右孩子左子树的右孩子应该对比右子树的左孩子。如果只做“左孩子对比左孩子”那检查的是“两棵树是否完全相同”而不是“是否对称”。3.2 递归双指针左右同时走既然比较的是成对节点递归函数就不能只接收一个root而是接收两个节点left和right它们代表当前要对比的镜像位置。class Solution: def isSymmetric(self, root): if not root: return True return self.compare(root.left, root.right) def compare(self, left, right): # 两个都为空对称 if not left and not right: return True # 其中一个为空或者值不相等不对称 if not left or not right or left.val ! right.val: return False # 外侧比较left.left 和 right.right outside self.compare(left.left, right.right) # 内侧比较left.right 和 right.left inside self.compare(left.right, right.left) return outside and inside终止条件的顺序很重要先判断“都为空”这是对称的再判断“一个空一个不空”直接返回False最后判断值不等也返回False。很多人在判断空节点时写反把“一个空一个不空”漏了导致访问空节点的属性时报错。记住空节点是所有递归的终点必须先处理干净。这个递归思路本质上用的是后序遍历框架先递归处理左右子节点拿到结果后再用and组合返回给上层。因为对称信息必须从底层往上汇总所以后序天然适合这道题。3.3 迭代法队列成对入队不用递归也能做核心思路是设置一个队列每次从队头取出两个需要比较的节点再把它们的“镜像对应关系”成对放进队尾from collections import deque class Solution: def isSymmetric(self, root): if not root: return True q deque() q.append((root.left, root.right)) while q: left, right q.popleft() if not left and not right: continue if not left or not right or left.val ! right.val: return False # 注意入队的配对方向 q.append((left.left, right.right)) q.append((left.right, right.left)) return True我用的是元组建对入队也可以用两个队列分别存left和right但那样容易在出队时搞混出队的顺序稍有错位就会出错。成对存储更稳写的时候不易乱。这里的关键仍然是“对比的配对关系”外侧、外侧入一队内侧、内侧入一队。每次弹出的两个节点就是需要比较的镜像节点。3.4 常见误区对称判断和相等判断的区别我把两种判断放在一起对比方便区分判断类型对比的配对方式终止条件两棵树是否相等left.left vs right.leftleft.right vs right.right都为空则相等一空一不空或值不等则不等两棵树是否对称left.left vs right.rightleft.right vs right.left都为空则对称一空一不空或值不等则不对称相等是“同方向对比”对称是“反方向对比”。这个区别想清楚代码就不容易写反。4. 104/111最大最小深度深度的本质与终止条件最大深度和最小深度放在一起刷是因为它们共用同一套深度计算逻辑但最小深度的终止条件藏着一个很隐蔽的坑。先搞清楚基本概念。4.1 深度还是高度傻傻分不清楚深度从根节点往下数根节点深度是1孩子深度是2。高度从叶子节点往上数叶子节点高度是1父节点高度是孩子高度再加1。根节点的高度 整棵树的最大深度。所以求最大深度可以用后序遍历的思路先算出左右子树的高度再取最大值加1得到当前节点的高度。这一套逻辑在104题里非常顺。4.2 最大深度后序递归一行逻辑直接看代码class Solution: def maxDepth(self, root): if not root: return 0 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) return max(left_depth, right_depth) 1递归逻辑可以理解为当前节点为空深度为0否则先求左子树的最大深度再求右子树的最大深度取较大的那一个加上当前节点这一层就是整棵树的最大深度。这个代码极度简单但有一个细节我刚开始常错容易忘记加1。如果写成return max(left_depth, right_depth)每一层都少算自己这个节点最后根节点算出来就会比真实深度少1。检查边界一棵只有根节点的树left_depth0right_depth0正确的返回值应该是1不加1就成了0一眼就能看出问题。4.3 最小深度最大的坑在“叶子节点”定义最小深度求的是从根节点到最近叶子节点的最短路径上的节点数量。注意这里的重点是“叶子节点”即左右孩子都为空的节点。很多同学第一次写会模仿最大深度# 错误示范 def minDepth(self, root): if not root: return 0 return min(self.minDepth(root.left), self.minDepth(root.right)) 1这个写法在“左右孩子都存在”的普通树上碰巧能过但只要遇到单链树就会出错。比如一棵树只有左孩子一路向下1 - 2 - 3。根节点1的右子树为空错误代码中minDepth(root.right)0于是结果变成min(2, 0)11也就是认为深度是1。可是1不是一个叶子节点真正最近的叶子是3最小深度应该是3。正确做法是当某个孩子为空时不能把空的那边深度当作0参与比较因为空子树里没有叶子根本不是一个候选路径。class Solution: def minDepth(self, root): if not root: return 0 # 左右孩子都为空当前节点是叶子深度为1 if not root.left and not root.right: return 1 # 只有左孩子不为空只能走左子树 if not root.left: return self.minDepth(root.right) 1 # 只有右孩子不为空只能走右子树 if not root.right: return self.minDepth(root.left) 1 # 左右孩子都不为空取较小的深度 return min(self.minDepth(root.left), self.minDepth(root.right)) 1这里前三个条件都是在排除“空子树参与min比较”的情况。一旦某一边为空唯一的路径就是另一边所以直接返回另一边深度加1。只有当左右孩子都存在时才能放心用min取较小值。用单链树验证根节点1只有左子树not root.right为真返回minDepth(root.left)1一直递归到叶子3返回1再一路累加得到3。正确。4.4 层序解法遇到第一个叶子即可返回求最小深度用层序遍历有一种天然优势按层推进从上到下扫描遇到第一个叶子节点时它所在的层数就是最小深度。因为BFS一层一层往下走第一次遇到叶子一定在最短路径上。from collections import deque class Solution: def minDepth(self, root): if not root: return 0 q deque([root]) depth 1 while q: level_size len(q) for _ in range(level_size): node q.popleft() # 第一个叶子节点所在层就是最小深度 if not node.left and not node.right: return depth if node.left: q.append(node.left) if node.right: q.append(node.right) depth 1注意depth的更新时机处理完一整层之后再加1。如果把depth 1写在每一次出队循环里深度会被错误地扩大好几倍。最大深度如果也想用层序只需要完整遍历所有层最后返回depth不需要提前返回class Solution: def maxDepth(self, root): if not root: return 0 q deque([root]) depth 0 while q: level_size len(q) for _ in range(level_size): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) depth 1 return depth最大深度和最小深度用层序解法的区别就一句话最小深度遇到叶子直接返回最大深度要把所有层走完。5. 四道题的共性框架把遍历骨架变成解题模板刷完这四道题我最大的收获是二叉树题型再变解题框架就两套——递归遍历和层序遍历。把今天四道题放进框架里对比会看得非常清楚。5.1 递归四题对照表题目终止条件单层递归做了什么返回值226.翻转二叉树当前节点为空返回None交换左右孩子再递归返回处理后的当前节点101.对称二叉树左右都为空返回True一个为空或值不等返回False比较外侧和内侧用and合并结果返回布尔值104.最大深度当前节点为空返回0分别求左右子树深度取最大值加1返回当前子树的高度111.最小深度当前节点为空返回0叶子返回1单边为空时走另一边根据左右子树是否为空决定计算方式返回当前子树的最小深度这四个终止条件没有一个相同但思考路径一样先处理空节点再处理单层逻辑。把每个题当成一个“普通节点视角”去分析递归就好写很多。5.2 层序框架对比表层序遍历在这四道题里至少有三道可以套用题目层循环中的关键操作返回时机226.翻转二叉树出队时交换左右孩子整个队列处理完返回root104.最大深度完整遍历每一层depth加1所有层处理完返回depth111.最小深度出队时检查叶子depth从1开始遇到第一个叶子立即返回depth层序的好处是过程直观、不用纠结递归调用顺序但缺点是代码比递归长而且要注意队列边界。我个人的做法是先用递归写出正确解再用层序写一个迭代版两道题的代码一起提交相当于用不同角度验证同一套逻辑。5.3 什么时候选递归什么时候选层序以我今天刷完的体感可以给几条很实用的建议面试时优先写递归。代码短、逻辑直白三步走既有套路又好讲面试官容易跟上思路。求最小深度优先写层序。因为递归要处理单边为空的特殊情况稍不留神就踩坑层序只要“遇到第一个叶子就返回”几乎不可能写错。如果题目明确要求不能用递归或者树的深度可能非常大比如退化成链表用层序。递归在极端情况下可能栈溢出层序用队列就不存在这个问题。我刷题时习惯两种解法都提交一遍因为训练营的打卡不仅要求AC还要理解透彻。多写一遍迭代法对递归的理解往往也会更深刻。6. 训练营第12天常见错误与实战经验最后总结一下当天我亲眼见过、或者自己踩过的坑给后来人提个醒。6.1 四个容易犯的错误错误点具体表现正确解法翻转二叉树用中序交换语句夹在两个递归调用之间改成前序或后序交换语句放在递归前/后均可对称二叉树比较方向搞反比较left.left和right.left外侧比left.left和right.right内侧比left.right和right.left最大深度忘加1return max(left, right)必须写成max(left, right) 1最小深度直接套min单链树时返回1先判断左右孩子是否为空空子树不能参与min比较这些错误都不是纯粹粗心而是对递归终止条件和遍历时机理解不到位。每错一次都值得花几分钟把递归展开图画一遍。6.2 在纸上跑递归一种排错技巧递归改错不好改我分享一个笨但极有用的方法画递归展开图。拿最大深度举例画一棵只有三个节点的树1 / \ 2 3调用maxDepth(1)后会进入左子树maxDepth(2)。maxDepth(2)的左右孩子都是空各自返回0然后maxDepth(2)返回max(0,0)11。同理maxDepth(3)1。回到根节点返回max(1,1)12。把这层关系写成列表空节点0节点2max(0,0)11节点3max(0,0)11节点1max(1,1)12只要脑子里能把这种自底向上的计算过程走一遍递归代码就不容易写错。很多“玄学错误”比如最小值算成1、忘记加1都能靠这个方法揪出来。6.3 给训练营同期的建议如果你今天打卡到这里我建议不要急着做下一批题。先用20分钟把226、101、104、111这四道题从题解里截出来盖上题解独立写一遍。写不出来的回到递归三部曲重新分析写出来但运行报错的用上面的递归展开图方式调试。直到四道题都能在20分钟内完成再进入后面的平衡二叉树这种综合题整体会轻松很多。我当天就是这么做的实测对后续刷题帮助非常大。