代码随想录算法训练营第十二天内容正好落在二叉树上。这一天三道题226.翻转二叉树、101.对称二叉树、111.二叉树的最小深度全部要求用递归法解决。这三道题在LeetCode上难度都不算高但它们非常能检验一个人对递归的理解深度——代码行数很少可一旦递归函数的参数、终止条件、单层递归逻辑这三块里有一块想岔了运行结果就是错的而且debug起来特别费劲。这篇记录把三道题的递归思路一步步拆开也把我训练营期间反复踩过的坑一并说清楚希望给正在刷二叉树的你一些参考。1. 三道题为什么值得放在同一天练递归框架的统一性先说一个很多刷题新手容易忽略的点二叉树递归题并不需要你背很多种模板。绝大多数题包括这三道本质都是同一个递归框架在三个不同位置做了改动。我习惯把递归解法拆成三块来审视递归函数的参数与返回值、终止条件、单层递归逻辑。这个拆法也是代码随想录里反复强调的递归三部曲训练营十二天这几道题正好把这三块的变化空间全部覆盖了。226.翻转二叉树单层递归逻辑里做交换递归参数和终止条件都是最基础的那一套。101.对称二叉树递归参数从一个节点变成两个节点终止条件的分支变多单层逻辑从处理一个节点变成比较一对节点。111.二叉树的最小深度参数和单层逻辑都常规但终止条件里藏着巨大的坑——你不能想当然地套最大深度的模板去取最小值。所以你会发现这三道题放在同一天不是随机的它们是一个渐进的难度阶梯。第一天能把递归三部曲模板吃透第二天这三道题就是用它做变式。反过来如果直接刷三道题却不理解这个框架你很容易陷入背题的状态每道题好像都会写但换一道还是不会。训练营第十二天的练习建议是不要急着写代码先把三道题各自的递归三部曲在纸上列出来。我当时把这个动作当走过场结果后面在111题上被折腾了很久。现在回头看这一步省不得。2. 226.翻转二叉树递归交换左右孩子的两种写法翻转二叉树的题意很直白把每个节点的左右孩子互换。LeetCode给的例子也很直观一棵二叉树翻转过来从视觉上看就是左右镜像。但真正动手写递归时有几个细节很值得琢磨。2.1 递归三步走分析先套递归三部曲。第一步确定递归函数的参数和返回值。翻转操作最终要返回翻转后的根节点所以返回值是TreeNode参数就是当前节点root。第二步确定终止条件。当前节点为空的时候直接返回None不需要做任何翻转。第三步确定单层递归逻辑。这一层要做的事情非常明确交换当前节点的左右孩子。至于交换之后要不要继续递归翻转子树当然要。这里就出现了两种写法上的选择。一种叫前序翻转先交换当前节点左右孩子再递归处理左子树和右子树。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(root): if not root: return None invertTree(root.left) invertTree(root.right) root.left, root.right root.right, root.left # 后交换 return root两种写法结果完全一样。前序是从上往下翻转后序是从下往上翻转。你可能会疑惑到底该用哪个我的经验是随缘选一种自己顺手的记住就好。真正需要注意的是下面这个中序陷阱。2.2 中序遍历写法为什么容易翻车如果按照中序遍历的顺序去写先递归处理左子树然后交换左右孩子再递归处理右子树会得到什么结果# 错误示范 def invertTree(root): if not root: return None invertTree(root.left) # 先处理左子树 root.left, root.right root.right, root.left # 交换 invertTree(root.right) # 再处理右子树 return root问题出在最后一行。交换之后原本的右子树已经被换到左边此时root.right指向的是原来的左子树。而这棵左子树在函数开头已经被递归翻转过一次了。现在你又翻转它第二次。结果是原来左子树里的节点被翻了两次原右子树反而一个都没翻到。整个树最终是错的。我最初写这道题时用的是中序思路测试用例跑挂了花了一段时间才意识到问题不在终止条件而在遍历顺序和交换操作的耦合上。这里给一个建议翻转二叉树优先用前序或后序别用中序。倒不是中序完全不能写而是需要额外记录一个临时节点绕过被换过来的子树已经被处理过这个坑但那样代码就绕了没必要。2.3 层序解法和其他细节其实用层序遍历BFS也可以解这道题每一层遍历到的节点都交换一下左右孩子。递归法本身在这个问题上没有性能优势但作为训练营第12天的题练习重点就是递归所以我建议先用递归写通再看层序。最后说一个我踩过的低级错误交换时没有保存引用。比如很多人会先写root.left root.right然后想当然地写root.right root.left这时候root.left已经被覆盖成原来的右子树了结果左右两边全变成原右子树。要避免这个问题可以借助Python的元组交换语法一行root.left, root.right root.right, root.left就完事或者用临时变量先存一下。3. 101.对称二叉树递归参数从单节点变成双节点翻转二叉树解决的是一棵树倒过来长什么样对称二叉树解决的是两棵树是不是互为镜像。这两道题放一起刷真的很容易混但它们其实是两个完全不同的方向。3.1 对称判断的本质是镜像比较对称二叉树的定义是什么一棵二叉树以根节点为轴左子树和右子树互为镜像。注意互为镜像这四个字。一棵树的左子树的左孩子要和右子树的右孩子比较左子树的右孩子要和右子树的左孩子比较。这个外侧对外侧、内侧对内侧的映射关系是整道题的核心。想明白这一点递归函数就很好写了。3.2 递归参数为什么要传两个节点因为要比较的是两棵树左右子树递归函数就不能只接收一个根节点而是需要接收两个节点。我在训练营里见过不少同学卡在这一步他们想的是能不能把左子树翻转一下然后和右子树比较可以但那已经不是对称判断了而且多一次不必要的树修改。正确的递归函数签名是比较left节点和right节点是否对称。这个函数做的事情是判断这两个节点能不能形成镜像关系。def compare(left, right): pass接下来处理终止条件。这里的分支比翻转二叉树要多我建议按下面这个顺序写不容易漏。3.3 终止条件的完整分支left为空right也为空说明两个子树都到底了是对称的返回True。left为空right不为空结构上就不对称返回False。left不为空right为空同样不对称返回False。两个都不为空但值不相等内容不对称返回False。两个都不为空且值相等才往下继续递归比较。很多人的第一版代码只写了条件5没处理空指针情况结果运行时报NoneType没有.val属性。这个问题的根源是对递归的终止条件理解不完整递归不是无限向下走的每个分支的出口都要考虑节点为空这个终态。把上面的分支整理成代码就是def isSymmetric(root): if not root: return True return compare(root.left, root.right) def 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 # 外侧: left.left 与 right.right # 内侧: left.right 与 right.left return compare(left.left, right.right) and compare(left.right, right.left)3.4 最容易错的地方这道题最容易错的地方不是终止条件而是最后一行递归参数的对应关系。我第一次写的时候直接写了compare(left.left, right.left)因为在翻转二叉树里我习惯了左右呼应结果测试用例直接挂掉。后来画了一下递归展开图才意识到左子树的左孩子应该和右子树的右孩子比也就是left.left配right.right左子树的右孩子配右子树的左孩子即left.right配right.left。这个交叉对应才是镜像对称的关键。另外注意最后一行用的是and。两侧必须同时满足对称结果才为真。如果写成or语义就变成了只要有一侧对称就整体对称那是错的。这道题也体现了递归参数设计的重要性同样一个递归框架把参数从单节点改成双节点整个问题的表达方式就变了。刷题到后面你会发现很多树相关的题目比如判断两棵树是否相同也是这个套路。4. 111.二叉树的最小深度终止条件里的经典陷阱最小深度这道题表面上比前两题还简单一棵二叉树从根节点到最近叶子节点的最短路径上的节点数量。可是递归实现的时候很多人直接套最大深度模板写成min(left, right) 1然后提交报错。这一整段就是讲清楚为什么不能这么写。4.1 最大深度与最小深度的本质区别先看最大深度的递归模板def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) 1这个写法成立的原因在于最大深度看的是最远的那条路max天然能忽略掉空子树的干扰。一棵树左子树为空、右子树很深max(0, 深度)取右子树的深度没有任何问题。但最小深度不能这么干。如果照搬模板写min(minDepth(root.left), minDepth(root.right)) 1会出现什么情况考虑一棵只有一个右孩子的树根节点2右孩子3。调用minDepth(root.left)返回0minDepth(root.right)返回1min(0, 1) 1 1于是你得出最小深度是1。这就错了因为根节点根本不是叶子节点它还有右孩子正确的最小深度应该是2。问题就出在root.left为空并不意味着这里就是树的尽头——它右子树还有路。而min会把那个深度0当成一条合法路径直接拉到最浅值。4.2 正确的递归终止条件设计所以正确的做法是把当前节点为空和当前节点是叶子节点分开处理还要单独照顾只有单侧孩子的情况。思路如下节点为空返回0。节点没有左右孩子叶子节点返回1。左孩子为空右孩子不为空只能沿着右子树走返回minDepth(root.right) 1。右孩子为空左孩子不为空只能沿着左子树走返回minDepth(root.left) 1。左右孩子都不为空才可以用min(minDepth(root.left), minDepth(root.right)) 1。写成代码def minDepth(root): if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return minDepth(root.right) 1 if not root.right: return minDepth(root.left) 1 return min(minDepth(root.left), minDepth(root.right)) 1这段代码看着分支多但其实每一条都对应一个明确的递归出口不会漏。4.3 一个常见的替代写法也有同学用另一种写法把左右孩子为空的情况提前过滤掉def minDepth(root): if not root: return 0 left minDepth(root.left) right minDepth(root.right) if not root.left: return right 1 if not root.right: return left 1 return min(left, right) 1两种写法的核心逻辑一样都是以是否叶子节点和是否有单侧空子树作为判断依据。我个人更推荐第一种因为终止条件写得更直白不容易漏分支。顺带一提如果追求效率最小深度也可以层序遍历第一次遇到叶子节点直接返回当前层数。递归法的时间复杂度同样是O(n)但层序在遇到浅叶子时会更早返回。不过既然训练营这一天要求的核心是递归法就先不扩展BFS讲了。5. 实战复盘递归法常见的三类错误与debug思路三道题单独讲完再把这些天的代码提交记录和debug过程汇总一下。递归题写错翻来覆去就那么几个原因我把它们分类列出来方便你们对号入座。5.1 递归函数没写清楚返回值和return位置这是最基础也最常见的一类错误。三题里翻转二叉树返回的是TreeNode对称二叉树返回的是bool最小深度返回的是int。返回值类型不同但有一个共同点递归调用的结果必须被接住或者直接参与return。对称二叉树那个最后的return compare(...) and compare(...)就是典型如果你分两行写先调用compare(外侧)再调用compare(内侧)却忘了把结果合并返回函数就会走到末尾隐式返回None导致主函数拿到的不是bool而是空值。我在训练营里见过好几个同学卡在这种极其隐蔽的缺失return上。5.2 终止条件不完整导致空指针对称二叉树里两个节点都为空时返回True但如果你只判断了一个为空就返回False就会让left.val访问在不存在的节点上报错。最小深度里如果你只写if not root: return 0不处理单侧空子树的情况返回的结果就会错得离谱。这里有一个排查技巧在递归函数开头打印当前访问的节点值跑一遍小规模的测试树看看递归进入的路径是否和你预期一致。打印出来的调用顺序会直接暴露终止条件遗漏的问题。5.3 单层递归逻辑想岔了翻转二叉树的中序陷阱对称二叉树的交叉对应最小深度的min误用本质上都是这一层递归到底要干什么没想清楚。这句话说出来容易但真正写代码时人很容易被前一天的题解带偏。我的建议是每道题写完自己在注释里写一句话概括单层逻辑。比如对称二叉树就写比较左节点的外侧与右节点的外侧同时比较左节点的内侧与右节点的内侧写完再对照代码看一不一致。这个动作很花时间但能根治记得住模板、套不对场景的问题。5.4 小规模用例 画栈推演是debug神器如果本地跑测试用例报错别急着看题解先构造一棵只有三个节点的树手动推演。比如对称二叉树报错时可以画一个左右孩子不对称的三节点树把递归展开写下来。栈的每一层对应哪些节点、会走到哪个分支画完你就知道问题出在哪了。我在训练营第十二天的项目复盘里记录过一句话递归题的bug通常不在递归本身而在递归之前的假设。你把假设写清楚bug基本能自己浮出来。最后再分享一个实际操作中的体会这三道题不要只写一遍。第一天用递归写第二天用层序遍历再写一遍第三天可以尝试把对称二叉树和翻转二叉树的解法对照着看。同一个知识点从不同角度反复过记忆会比单纯刷量牢固得多。训练营十二天只是万里长征的中间站递归这个能力值得多花几天打磨。