企业官网建设流程全解析

代码随想录训练营到了第12天，二叉树开始上强度了。今天的四道题——翻转二叉树、对称二叉树、二叉树的最大深度、最小深度，表面上是四道独立题目，实际全是“遍历框架”的变体。如果你像我一样，前几天的“二叉树的遍历”已经练到闭眼能写递归，今天应该只花一个多小时；如果递归还没吃透，这一天刚好给你一个集中突破的机会。这篇复盘文章，我把递归三部曲、层序模板、还有当天踩过的坑全整理出来，希望能帮后面打卡的同学少走弯路。

1. 为什么这几道题值得单独练一天

训练营把226、101、104、111这四道题放在同一天，不是随机拼凑。它们都有一个共同特征：不要求你发明新遍历方式，而是把已经学过的递归遍历和层序遍历，套到不同的业务逻辑上。换句话说，前几天的题目考查“能不能写出遍历”，从这天开始考查“能不能用好遍历”。

1.1 四道题其实都是遍历的变形

把四道题摊开看，本质非常统一：

• 226.翻转二叉树：遍历到任意一个节点时，交换它的左右孩子。用前序、后序、层序都可以，目的只是“访问到每一个节点，然后做一次交换”。
• 101.对称二叉树：不是单独遍历一棵树，而是同时遍历左右两棵子树，比较它们是否互为镜像。这是遍历框架的升级版——之前是单指针走一棵树，这次是双指针同时走两棵树。
• 104.二叉树的最大深度：遍历过程中记录当前节点的深度，到叶子节点时更新答案。递归解法里用的是后序遍历，因为要先把左右子树的深度算出来，才能推出当前节点的深度。
• 111.二叉树的最小深度：逻辑上和最大深度对称，但它有一个特别容易踩的坑：“最小”不能简单用min套，因为只有叶子节点才配作为终点。

当你意识到这四道题都在“遍历”这个地基上变形，就不需要再背额外的东西，只需要把递归三部曲和层序框架吃透。

1.2 递归三部曲：当天真正的主角

刷二叉树的递归题，我一直觉得有一套万能心法，代码随想录里管它叫“递归三部曲”，我自己用下来确实能覆盖90%的树问题：

1. 确定参数和返回值：这个递归函数要传什么进去，最后要向调用方返回什么。
2. 确定终止条件：什么时候该直接返回，不再向下递归。
3. 确定单层递归逻辑：当前这一层节点该做什么事，然后如何调用下一层。

听起来抽象，其实很像公司里的任务派发。管理层（当前节点）不需要自己干完整棵树，只需要处理自己这一层的事情，然后把左半、右半的任务分别交给两个下级，下级再往下派。每个层级只关心自己的局部动作，组合起来就是整棵树的答案。

对应到代码上，二叉树的递归题大多长这样：

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)

假设根节点是A，A的左孩子是B，右孩子是C。执行顺序是这样的：

1. 先递归翻转A的左子树B；
2. 交换A的左右孩子，此时A.left变成了C，A.right变成了B；
3. 再递归翻转A.right，而这时A.right是原来的B，B会被再翻一次。

结果是：原来的右子树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

终止条件的顺序很重要：

1. 先判断“都为空”，这是对称的；
2. 再判断“一个空一个不空”，直接返回False；
3. 最后判断值不等，也返回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 常见误区：对称判断和相等判断的区别

我把两种判断放在一起对比，方便区分：

相等是“同方向对比”，对称是“反方向对比”。这个区别想清楚，代码就不容易写反。

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_depth=0，right_depth=0，正确的返回值应该是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)+1=1，也就是认为深度是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 递归四题对照表

这四个终止条件没有一个相同，但思考路径一样：先处理空节点，再处理单层逻辑。把每个题当成一个“普通节点视角”去分析，递归就好写很多。

5.2 层序框架对比表

层序遍历在这四道题里，至少有三道可以套用：

层序的好处是过程直观、不用纠结递归调用顺序，但缺点是代码比递归长，而且要注意队列边界。我个人的做法是：先用递归写出正确解，再用层序写一个迭代版，两道题的代码一起提交，相当于用不同角度验证同一套逻辑。

5.3 什么时候选递归，什么时候选层序

以我今天刷完的体感，可以给几条很实用的建议：

• 面试时优先写递归。代码短、逻辑直白，三步走既有套路又好讲，面试官容易跟上思路。
• 求最小深度优先写层序。因为递归要处理单边为空的特殊情况，稍不留神就踩坑；层序只要“遇到第一个叶子就返回”，几乎不可能写错。
• 如果题目明确要求不能用递归，或者树的深度可能非常大（比如退化成链表），用层序。递归在极端情况下可能栈溢出，层序用队列就不存在这个问题。

我刷题时习惯两种解法都提交一遍，因为训练营的打卡不仅要求AC，还要理解透彻。多写一遍迭代法，对递归的理解往往也会更深刻。

6. 训练营第12天常见错误与实战经验

最后总结一下当天我亲眼见过、或者自己踩过的坑，给后来人提个醒。

6.1 四个容易犯的错误

这些错误都不是纯粹粗心，而是对递归终止条件和遍历时机理解不到位。每错一次，都值得花几分钟把递归展开图画一遍。

6.2 在纸上跑递归：一种排错技巧

递归改错不好改，我分享一个笨但极有用的方法：画递归展开图。

拿最大深度举例，画一棵只有三个节点的树：

1 / \ 2 3

调用maxDepth(1)后，会进入左子树maxDepth(2)。maxDepth(2)的左右孩子都是空，各自返回0，然后maxDepth(2)返回max(0,0)+1=1。同理maxDepth(3)=1。回到根节点，返回max(1,1)+1=2。

把这层关系写成列表：

• 空节点：0
• 节点2：max(0,0)+1=1
• 节点3：max(0,0)+1=1
• 节点1：max(1,1)+1=2

只要脑子里能把这种自底向上的计算过程走一遍，递归代码就不容易写错。很多“玄学错误”，比如最小值算成1、忘记加1，都能靠这个方法揪出来。

6.3 给训练营同期的建议

如果你今天打卡到这里，我建议不要急着做下一批题。先用20分钟把226、101、104、111这四道题从题解里截出来，盖上题解，独立写一遍。写不出来的，回到递归三部曲重新分析；写出来但运行报错的，用上面的递归展开图方式调试。直到四道题都能在20分钟内完成，再进入后面的平衡二叉树这种综合题，整体会轻松很多。我当天就是这么做的，实测对后续刷题帮助非常大。