训练营第12天，三道题摆在一块儿的时候，我明显感觉到递归法在二叉树题目里那种“绕不开”的存在感：226.翻转二叉树、101.对称二叉树、111.二叉树的最小深度，题目看起来一个比一个短，但每一道都在逼你想清楚递归的终止条件、返回值和单层逻辑。尤其是最小深度那道题，我第一次提交就被[1,null,2]这种链表形态的树给坑了，错得心服口服。
这篇文章就把这三道题一次说透。我会从思路拆解讲到代码实现，再到我实际刷题时踩过的坑和排查方法，适合刚学完二叉树遍历、正准备刷递归法题目的同学。如果你已经被“写递归函数”这件事折磨过，或者写过Runtime Error但死活找不到原因，这篇内容应该能帮你少走不少弯路。
1. 为什么是这三道题：递归法在二叉树里的“三板斧”
刷题不能只盯着题目本身。代码随想录把这三道题放在同一期训练营里，是有意的安排——它们分别考察了递归法的三种典型用法：对子树做修改、对两棵子树做比较、对子树深度做累计。这三板斧覆盖了绝大多数二叉树递归题的底层逻辑。
1.1 递归法的“三要素”必须先刻在脑子里
写递归题之前，先把这套框架过一遍：第一，终止条件是什么，比如节点为空、节点是叶子、已经找到目标；第二，返回值是什么，是处理后的节点指针，还是一个布尔值，还是一个整数深度；第三，这一层递归要完成什么操作，比如交换左右节点、比较两个节点值、计算左右子树深度。很多时候卡题不是思路不清楚，而是这三个问题没有在动手前回答完。
以翻转二叉树为例，终止条件是空节点直接返回；返回值应该是翻转后的当前节点指针；单层逻辑就是交换左右孩子，再递归翻转左右子树。这个框架一旦定下来，代码基本就是照着填空。对称二叉树则是返回值变成布尔值，终止条件要同时考虑两个节点的四种情况。到了最小深度，返回值变成整数，终止条件还多了一个“遇到叶子节点就返回1”的判断。三道题恰好覆盖了三种返回类型，这就是训练营这样排期的深意。
1.2 二叉树的遍历顺序决定了递归的写法
递归法和二叉树的遍历顺序是死死绑定在一起的。前序遍历是“先处理当前节点，再递归孩子”，中序遍历是“先左、再中、再右”，后序遍历是“先递归孩子，再处理当前节点”。翻转二叉树用的是前序或后序，对称二叉树本质上依赖后序的“由下而上汇总”，最小深度则需要左、右子树的信息都回来之后才能做决策。
这也是为什么很多人写翻转二叉树时，会把中序遍历写上，结果发现树“翻完又翻回来了”。中序遍历在遍历完左子树之后处理当前节点，此时交换左右孩子，但接下来代码要遍历的是“右孩子”，而它已经被换成了原来的左子树——这个左子树刚刚才被翻转过一次，于是就会出现一部分节点被翻转两次、一部分始终没翻的情况。后面我会专门展开讲这个坑。
1.3 这一期和前后题目怎么衔接
这三道题做完之后，你会发现自己看后续题目的眼光变了。比如后面做104.二叉树的最大深度时，你拿到的代码和最小深度几乎一模板一样；做112.路径总和时，你会意识到它也是递归返回值当判断用的典型场景；做236.二叉树的最近公共祖先时，你会体会到“后序遍历+返回值”的组合拳有多爽。可以说这三道题是二叉树递归法的地基，今天多花点时间把细节抠清楚，后面会省很多事。
2. 226.翻转二叉树：最直观的递归入门题
这道题在LeetCode上叫Invert Binary Tree，翻转一棵二叉树，意思就是每个节点的左右孩子全部交换。题目一句话，但实现的细节并不像描述那么随意。我第一次交的时候用的中序遍历，结果翻了个寂寞，后来才明白问题出在遍历顺序上。
2.1 解题思路与前序后序的选择
翻转一棵树，操作对象是每个节点的左右孩子指针。最直接的逻辑：对于当前节点，先把它的left和right换掉，然后递归翻转左子树，再递归翻转右子树。这就是前序遍历的写法——先处理自己，再处理孩子。
TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; }这段代码为什么是对的？因为swap交换的是当前节点的两个孩子指针，交换完之后，左孩子指针指向的是原有的右子树，右孩子指针指向的是原有的左子树。接下来递归调用invertTree(root->left)，处理的实际是原来的右子树；再递归invertTree(root->right)，处理的是原来的左子树。这样一来，每一棵子树都只被处理一次，翻转正确。
换成后序遍历也同样可行：先递归翻转左子树，再递归翻转右子树，最后交换两个已经翻转完成的子树。这两种顺序都没有问题，因为对每个节点来说，交换操作和递归操作互不干扰。
但中序遍历为什么不行？我把代码写出来给你看：
// 错误的写法：中序遍历翻转 TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; invertTree(root->left); swap(root->left, root->right); invertTree(root->right); return root; }这段代码的执行过程很微妙。以一棵只有三层的小树为例：先递归翻转左子树，左子树被正确翻完了；回到根节点，交换左右孩子；此时根节点的右孩子是“原来的左子树”——它已经被翻转过一次了。代码接着递归处理root->right，等于把这个已经翻转过的子树又翻了一遍；而根节点“原来的右子树”被换到了左边，压根没有进入递归。结果就是：有些子树被翻了两次，有些子树一次都没被翻。画个图模拟一下就会看得非常清楚。
2.2 交换节点的一个小细节
很多C++初学者在写交换时，会习惯性地写一个临时变量：
TreeNode* temp = root->left; root->left = root->right; root->right = temp;这样写完全没问题，只是std::swap更简洁。但这里有一个容易被忽略的点：swap交换的是指针的值，不是TreeNode对象本身。也就是说，我们改的是当前节点的left和right成员，整棵树的内存结构并没有复制。空间复杂度是递归栈的深度，而不是复制一棵树的开销，这一点心里要有数。
2.3 用层次遍历（迭代法）也能翻转
递归法写起来丝滑，但如果你想换个思路，层次遍历同样可以完成翻转：用队列存节点，出队一个节点就交换它的左右孩子，再把非空孩子入队。这个做法本质上和递归一样，每个节点只处理一次，只是把递归栈换成了显式队列。建议把两种解法都写一遍，因为后面很多二叉树题目，你都需要在“递归”和“迭代”之间灵活切换。
from collections import deque def invertTree(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 rootPython写起来更短，关键就一行的node.left, node.right = node.right, node.left。不管用什么语言，思路是一样的：每个节点必须且只能被翻一次。
3. 101.对称二叉树：用递归同时比较两棵子树
翻转二叉树之后，紧接着来了一道“镜像”题。对称二叉树要求判断一棵二叉树是不是镜像对称的，也就是说，根节点的左子树和右子树，从外到内、从内到外都要一样。比如[1,2,2,3,4,4,3]是一棵对称树，而[1,2,2,null,3,null,3]不是。这道题的难点在于，你不能再盯着单个节点看，而要同时拿两个节点来比。
3.1 为什么这道题要用“后序”思维
初看这道题，很多人会想：我是不是可以递归左子树和右子树，分别判断它们是不是对称树？这个思路是错的。一棵树的左子树本身可能非常不对称，但只要它的镜像能和右子树对应上，整棵树依然是对称的。关键不在“单棵子树长什么样”，而在“两棵子树拼在一起成不成镜像”。
所以递归函数的参数应该是两个节点：left和right。判断逻辑分成四步，这种分步思考的方式对新手特别友好：
- 两个节点都为空，说明这一层匹配，返回
true； - 一个为空一个不为空，说明结构不对称，返回
false； - 两个都不为空，但值不相等，返回
false； - 两个都不为空且值相等，继续往下比：
left.left和right.right比（外侧），left.right和right.left比（内侧）。
第四步为什么要分“外侧”和“内侧”？你可以想象一面镜子放在根节点上：左子树的左孩子，对应的是右子树的右孩子；左子树的右孩子，对应的是右子树的左孩子。方向反了，镜像就不成立。代码里必须先递归调用外侧和内侧，再把两个布尔结果合并返回，这就是典型的后序遍历思路——先收集子树的信息，再对当前层做判断。如果你先 return，后面的递归就不会执行，整个判断就不是完整的。
bool compare(TreeNode* left, TreeNode* right) { if (left == nullptr && right == nullptr) return true; else if (left == nullptr || right == nullptr) return false; else if (left->val != right->val) return false; bool outside = compare(left->left, right->right); bool inside = compare(left->right, right->left); return outside && inside; } bool isSymmetric(TreeNode* root) { if (root == nullptr) return true; return compare(root->left, root->right); }3.2 注意别和“搜索二叉树”的概念混淆
刷题时有个热词叫搜索二叉树（BST），特别容易和对称二叉树混在一起。BST 的定义是：左子树所有节点值小于根节点，右子树所有节点值大于根节点，并且左右子树本身也是BST。但是对称二叉树完全不关心值的大小顺序，只关心左右两边是不是镜像。一棵BST可以是完全不对称的，比如[2,1,3,null,null,4,5]不是对称树，但它完全可以是合法的BST。做这一题的时候别用“左小右大”的思维去套，会把自己绕晕。
3.3 用队列做迭代版本：同一个套路，两种写法
对称二叉树也可以用迭代法实现。思路是：用队列成对地把节点放进去。先放左孩子和右孩子，出队两个节点进行比较；再把left->left和right->right放进去，把left->right和right->left放进去。这里的顺序不能乱，因为镜像比较的逻辑和递归是完全一致的。迭代法唯一的区别是把递归栈换成了队列，好处是避免了递归过深时的栈溢出风险，坏处是代码可读性稍微差一点。两种写法建议都掌握。
from collections import deque def isSymmetric(root): if not root: return True q = deque([root.left, root.right]) while q: left = q.popleft() 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) q.append(right.right) q.append(left.right) q.append(right.left) return True这里要注意，continue和return False的区别。两个节点都为空时，说明这一层匹配完成，但队列里可能还有下一层的节点，所以要继续循环；只有出现“一个为空一个不为空”或“值不相等”时，才可以提前判死刑。
4. 111.二叉树的最小深度：递归法最容易翻车的边界题
第三道题是求最小深度，题目定义是：从根节点到最近叶子节点的最短路径上的节点数量。叶子节点指的是没有孩子的节点。别看这道题只是一道深度题，它是我这三道里唯一提交失败过的，失败原因就是没有理解“叶子节点”这个限制。
4.1 最大深度与最小深度的关键差异
求最大深度，代码人人都能背下来：
return max(maxDepth(root->left), maxDepth(root->right)) + 1;如果照葫芦画瓢写最小深度，很容易写出：
return min(minDepth(root->left), minDepth(root->right)) + 1;这行代码放在一棵正常的满二叉树里，结果可能碰巧是对的。但一旦遇到[1,null,2]这种只有右子树没有左子树的情况，就会力出问题：根节点的左孩子为空，minDepth(nullptr)返回0；右孩子是节点2，minDepth(node2)返回1；整体结果是0 + 1 = 1。可是真实的树长这样：1 → 2，从根节点到叶子节点2的路径上明明有2个节点，最小深度应该是2，不是1。
问题就出在：null不是叶子节点。一棵树如果只有右孩子，左孩子的空指针根本不能算作一条“有效路径”的终点。所以必须分清楚：左子树为空时，要走右子树；右子树为空时，要走左子树；两边都为空时，说明当前节点就是叶子节点，返回1。
4.2 正确的递归写法与分类讨论
把逻辑落到代码上，最简单的方式是分情况讨论：
int minDepth(TreeNode* root) { if (root == nullptr) return 0; // 当前节点是叶子节点 if (root->left == nullptr && root->right == nullptr) return 1; int leftDepth = INT_MAX; int rightDepth = INT_MAX; if (root->left) leftDepth = minDepth(root->left); if (root->right) rightDepth = minDepth(root->right); return min(leftDepth, rightDepth) + 1; }这段代码的巧妙之处在于：把左右深度都初始化为INT_MAX，只递归存在的子树。如果当前节点只有左子树，那么右子树不参与比较，leftDepth是左子树的真实最小深度，整体返回leftDepth + 1；如果两个子树都不存在，说明当前是叶子，直接返回1。这种写法把所有情况都统一到了min里，不需要再额外写if (root->left)分支去递归判断，代码更清晰。
也可以写成更直白的版本：
int minDepth(TreeNode* root) { if (root == nullptr) return 0; if (root->left == nullptr && root->right == nullptr) return 1; if (root->left != nullptr && root->right == nullptr) return minDepth(root->left) + 1; if (root->left == nullptr && root->right != nullptr) return minDepth(root->right) + 1; return min(minDepth(root->left), minDepth(root->right)) + 1; }两种写法结果一模一样，你可以选自己更容易接受的版本。我个人的建议是：第一次做这道题时老老实实分四种情况写一遍，把边界条件想透了，之后再改成INT_MAX的简洁写法，这样不容易翻车。
4.3 迭代法为什么更适合这道题
使用层序遍历求最小深度其实更直观。因为层序遍历是一层一层往下扫的，当第一次遇到一个叶子节点时，当前的深度就是最小深度，直接返回即可，不需要把整棵树都扫完。而递归法不管三七二十一，要把所有分支都算一遍，浪费的时间在极端情况下可能是指数级的。
int minDepth(TreeNode* root) { if (root == nullptr) return 0; queue<TreeNode*> q; q.push(root); int depth = 0; while (!q.empty()) { int size = q.size(); depth++; while (size--) { TreeNode* node = q.front(); q.pop(); if (node->left == nullptr && node->right == nullptr) { return depth; } if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return depth; }如果面试时时间紧张，建议先写层序遍历，因为它不容易出现边界条件的坑；如果面试官要求用递归法，再切换到上面的分类讨论写法。两种方式都能过，但背后的思维模式完全不同，这也是算法训练营反复建议“一题多解”的原因。
5. 常见错误与排查技巧：递归写错时如何快速定位
刷这三道题时，我遇到过编译报错、逻辑错误、运行超时，甚至还有一次直接遭遇了Stack Overflow。这些错误本身不可怕，可怕的是不知道从哪里下手排查。这里分享一下我的排查方法，以及写递归代码时最容易犯的几个错。
5.1 运行时错误是怎么来的
先看一个最典型的场景：你写翻转二叉树时，递归调用了invertTree(root->left)，但忘记写终止条件，或者终止条件写了if (root->left == nullptr) return root;。这种条件下，递归到空节点时根本进不了函数体判断，代码会继续访问root->left的空指针，最终触发空指针访问或栈溢出。这类问题在LeetCode上报出来就是Runtime Error。
再比如对称二叉树，很多人写终止条件时习惯于先检查left->val != right->val，却忘了先判断左右是否为空。一旦left是空指针，left->val直接越界。正确顺序一定是先判空，再判值。这个顺序在写递归时是铁律，任何非空指针的成员访问都要放在判空之后。
另外一个隐蔽的坑是递归函数写成了死循环。最小深度那道题，如果你在某个分支里递归调用自己，却没改变传入的参数，会导致同一个节点被无限递归。调试的时候会发现程序一直不退出，CPU占用率飙升。这种情况一般是单层逻辑写错了，检查一下递归参数是否真的“更小了一层”。
5.2 调试技巧：用打印法看清递归过程
我强烈推荐一个土办法：在递归函数开头加一行打印，输出当前节点值和深度。比如翻转二叉树，可以在进入函数时打印"swap node: " + to_string(root->val)，运行一遍，你就能看到递归访问节点的顺序，从而判断自己的遍历顺序是不是想要的。
void debug(TreeNode* root, int depth) { if (root == nullptr) return; cout << string(depth * 2, ' ') << root->val << endl; debug(root->left, depth + 1); debug(root->right, depth + 1); }通常跑一个只有三四个节点的小测试用例就够了。如果打印出来的顺序和预期不符，那问题多半出在递归调用的顺序上；如果打印过程出现重复节点，那就说明出现了交叉引用或翻转了两次的“中序陷阱”。这个方法比我靠肉眼盯代码高效十倍，强烈建议在无助的时候先用起来。
5.3 别掉进“人肉递归”的坑
写这三道题时，我发现自己最常犯的毛病是想在脑子里把递归的调用栈完整过一遍。每次遇到递归就自己模拟一遍“进去、返回、再进去”，很快就晕了。后来我总结了一个经验：递归函数本身应该被当作一个已经正确实现的黑盒，你只需要保证三件事：终止条件正确，返回值类型统一，单层逻辑不会改变传入参数的约束。写完这三条，剩下的交给递归自身去处理。
打个比方，你写minDepth(root->left)时，不需要再问自己“这个函数是怎么一步步算出来的”，你只需要知道它返回的是左子树的最小深度。这种信任思维，是递归代码能写对的前提。如果发现结果不对，再来检查三要素，而不是逐行展开整个递归过程。
5.4 题目之间的迁移技巧
三道题做完之后，把它们放在一起复盘会发现一个规律：只要是“求深度、求路径、判断形态”这类二叉树问题，递归法的核心都在于如何用返回值表达子问题的结果。翻转二叉树返回的是处理后的节点，对称二叉树返回的是布尔判断，最小深度返回的是整数深度。想清楚返回值，再想递归逻辑，大方向就不会偏。
另外，如果你想把层序遍历练熟，我建议把这三道题全部用迭代法再做一遍。尤其是最小深度，用层序遍历实现会简单到让人怀疑是不是同一道题。用“先递归再迭代”的双解法去刷题，比只背一种答案扎实得多，这也是代码随想录训练营一贯的风格。
写在最后：我的三点实操体会
训练营第十二天这三道题，我实际刷下来的感受是：题目难度真的不算大，但每道题都精准击中了一个容易忽略的细节。翻转二叉树提醒你遍历顺序的重要性；对称二叉树逼迫你从“单个节点”的思维跳到“两棵子树”的思维；最小深度则是把空指针和叶子节点的概念差异变成了一道送命题。
如果你正在刷这一期的题，我建议你按照这个顺序来：先独立写三要素，再写代码，最后故意用错误的写法提交一次，看看输出错在哪里。比如把最小深度写成min(left, right) + 1，提交之后观察失败用例，你就能彻底理解为什么空子树不能参与最小值的比较。这种“故意犯错再纠正”的方式，比我单纯看题解的记忆要牢固得多。
我自己做题最大的收获，是学会了“信任递归”。不要把递归想成一种需要实时跟踪的复杂调用，而是要像使用库函数一样信任它的返回值。当你能写出简洁的递归停止条件，并且清楚地知道每一层返回什么，二叉树这一大类题目就算真正上道了。
