企业官网建设流程全解析

代码随想录算法训练营第十二天，内容正好落在二叉树上。这一天三道题：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 终止条件的完整分支

1. left为空，right也为空：说明两个子树都到底了，是对称的，返回True。
2. left为空，right不为空：结构上就不对称，返回False。
3. left不为空，right为空：同样不对称，返回False。
4. 两个都不为空，但值不相等：内容不对称，返回False。
5. 两个都不为空且值相等：才往下继续递归比较。

很多人的第一版代码只写了条件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)返回0，minDepth(root.right)返回1，min(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基本能自己浮出来。

最后再分享一个实际操作中的体会：这三道题不要只写一遍。第一天用递归写，第二天用层序遍历再写一遍，第三天可以尝试把对称二叉树和翻转二叉树的解法对照着看。同一个知识点从不同角度反复过，记忆会比单纯刷量牢固得多。训练营十二天只是万里长征的中间站，递归这个能力值得多花几天打磨。