代码随想录算法训练营进入第十二天三道题全是二叉树226. 翻转二叉树、101. 对称二叉树、111. 二叉树的最小深度。很多人一看到“递归法”三个字就发怵其实这三道题放在同一天非常讲究——它们不是简单地重复练习而是把递归的三种典型用法各练了一遍单棵树的遍历加操作、两棵子树的同步比较、以及返回值受边界条件约束的特殊处理。如果你正处于“题解看得懂、自己写就卡壳”的阶段这一天的内容值得反复嚼。这三道题的难度曲线也很友好。226 是最基础的递归结构101 把递归参数从“一个节点”扩展到“两个节点”111 则开始考验你对递归返回值和终止条件的掌控力。整个练下来你能明显感觉到递归不再是一个玄学概念而是一套可以刻画的操作流程。下面我把每道题的思考过程、标准写法和踩过的坑都拆开讲。1. 三道题为什么被排在训练营同一天1.1 先立住递归的“三要素”框架很多人练递归最大的问题是题目一变就不知道从哪下手。代码随想录的递归讲解里反复强调一个框架我概括成三个问题递归函数要返回什么参数要传什么什么时候停下来如果你在写递归前能回答这三个问题代码基本就写出来了一大半。返回值这道题我需要在树的每一层拿到什么结果是交换后的子树根节点是“是否对称”的布尔值还是最小深度这个整数参数我当前需要处理的范围是什么有时候是单个节点有时候需要同时传入两个节点让它们互相比较。终止条件什么情况下递归直接返回不再往下走是节点为空还是已经拿到了答案拿这三道题对照这个框架会特别清晰。226 的返回值是翻转后的子树根参数是当前节点终止条件是节点为空101 的返回值是“这两个子树是否对称”参数要同时传左节点和右节点终止条件是节点为空或值不相等111 的返回值是最小深度参数是当前节点终止条件是节点为空但这里多了对“单分支节点”的特殊判断。你会发现同一个框架三种不同的展开方式这就是训练营选这三题的价值所在。1.2 从“操作自己”到“比较两棵树”再到“边界控制”这三道题的关系是层层递进的。226 翻转二叉树是最纯粹的“单树操作”你只需要在遍历过程中把左右孩子交换一下递归的方向很直观适合用来建立“递归就是深度优先遍历”的肌肉记忆。到了 101 对称二叉树问题立刻升级你不再是从上往下走一棵树而是需要同时从两个方向出发比较“树的左侧”和“树的右侧”是否互为镜像。很多人第一次写这道题会愣住因为递归函数的参数突然变成了两个节点这个思维转换是递归能力的第一道坎。111 二叉树的最小深度则是另一类典型递归逻辑本身不复杂复杂度全在边界条件的处理上。你如果直接套“最大深度”的写法把 max 换成 min铁定出错。这题的坑在于“空子树”不能参与最小值比较——一个只有左孩子的节点它的右子树是空的但你不能认为它的最小深度是 1。这种“看起来简单、实际暗藏条件”的题目恰恰是面试官最喜欢拿来验基本功的。2. 226. 翻转二叉树递归的入门热身2.1 题目本质与直觉思维翻转二叉树的题目描述很直白给一棵二叉树的根节点把每一棵子树的左右孩子交换位置最终返回翻转后的根节点。说白了就是每个节点的左右子树都“镜像”一下整棵树变成自己的镜像。暴力一点的思路是遍历每个节点把它的左右孩子交换。遍历方式无所谓前序、后序、层序都能完成核心操作就一行swap(node-left, node-right);难点在于“什么时候交换”和“交换完还要处理什么”。如果你用递归交换完当前节点后还要继续对左右子树做同样的操作。而当你把交换放在递归之前或之后代码逻辑会出现微妙差异这里也是面试官最爱追问的点。2.2 前序递归与后序递归的标准写法后序递归是我个人最推荐理解的写法因为它的逻辑顺序和人类思考方式完全一致先把左子树整棵翻转好再把右子树整棵翻转好最后把这两个已经翻转完毕的子树交换位置。class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; // 后序先翻转左子树再翻转右子树最后交换 TreeNode* left invertTree(root-left); TreeNode* right invertTree(root-right); root-left right; root-right left; return root; } };前序递归则相反先交换当前节点的左右孩子然后递归处理左子树和右子树。因为交换发生在递归之前孩子位置已经换了所以递归处理时传的 left 和 right 是换完之后的节点逻辑依然成立。class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; swap(root-left, root-right); // 先交换 invertTree(root-left); // 再递归 invertTree(root-right); return root; } };两种写法都能通过时间都是 O(n)空间都是 O(n) 的最坏栈深度。区别只在思考角度你觉得哪种顺就用哪种但一定要理解另一种为什么也对。2.3 中序递归为什么是陷阱如果改用中序递归问题就来了。中序是“左-中-右”如果套前序的思路代码长这样class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; invertTree(root-left); // 左 swap(root-left, root-right); // 中交换 invertTree(root-right); // 右 return root; } };表面上看起来和前序没什么区别实际跑起来却会出错。原因是交换发生在递归左子树之后此时左子树已经翻转完毕交换之后原先翻转好的左子树被换到了右边而原先没处理的右子树被换到了左边。接下来递归右子树这时的“右子树”其实是已经翻转过的原左子树等于把它又翻转了一遍而原右子树待在左孩子的位置上永远没有被递归处理。结果就是根节点确实交换成功了但原右子树保持原样原左子树被翻了两遍等于没翻。整个树乱了套。这个坑特别隐蔽因为如果树的规模很小、结构对称肉眼扫描代码很容易骗过自己。我建议你哪怕不写中序解法也一定要把这个过程在纸上走一遍理解递归顺序和操作顺序的相互影响。2.4 不用递归也能翻转层序解法递归之外层序也叫广度优先解法同样直观。用队列逐层遍历每遇到一个节点就交换它的左右孩子。class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root nullptr) return nullptr; queueTreeNode* que; que.push(root); while (!que.empty()) { TreeNode* node que.front(); que.pop(); swap(node-left, node-right); if (node-left) que.push(node-left); if (node-right) que.push(node-right); } return root; } };这个解法没有递归压栈的深度风险推荐初次学习时把递归和层序各写一遍能帮你理解“遍历顺序”和“操作时机”并不是一回事。递归解决的是“怎么自然地顺着树的路径走”层序解决的是“按层逐个处理”。3. 101. 对称二叉树递归参数从“一个节点”变成“两个节点”3.1 先破除一个常见误区中序序列回文不等于对称看到对称二叉树很多人第一反应是“把树遍历一下看结果是不是回文”。尤其是中序遍历某些对称的树确实会输出回文序列于是有人想偷懒中序走一遍判断结果是否回文。这个思路是错的而且错得很经典。中序序列回文只能说明数值序列在“中序顺序”上对称无法保证树的左右结构真的互为镜像。我举个反例1 / \ 2 3 \ \ 3 2这棵树的中序遍历结果是 2, 3, 1, 3, 2确实是回文但树显然不对称——根节点的左孩子是 2右孩子是 3根节点的左右孩子值都不一样。所以“中序回文”既不充分也不必要判断对称必须从树的结构本身出发老老实实做结构比较。3.2 同步遍历两根子树的递归写法对称的核心是对于根节点的左子树和右子树要满足两两对应。比较的模型不是一棵树自己走而是两个节点同时往下走。所以递归函数要接收两个参数一个来自左子树一个来自右子树。比较逻辑分三层都为空对称返回 true。一个为空一个不为空结构不对称返回 false。值不相等内容不对称返回 false。如果前面都没问题就继续往下比较。注意比较方向左子树的左孩子 要跟 右子树的右孩子 比这是外侧左子树的右孩子 要跟 右子树的左孩子 比这是内侧。class Solution { public: 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.3 空节点的比较顺序为什么不能乱上面的代码里空节点的判断顺序是很有讲究的。必须先处理“都为空”和“一个为空”再去比较值。如果把“值不相等”的判断提到空判断之前一遇到空节点就会尝试读left-val直接触发空指针解引用程序立马崩掉。这个顺序问题看着基础但在递归里特别容易踩。我再强调一次任何时候在递归中访问节点的属性都必须先确认它不为空。处理空值的分支要放在最前面值比较的分支永远放在空判断之后。如果你刷题时遇到“运行时错误”十有八九是这个顺序写反了或者某个分支漏了空指针保护。3.4 用队列改成迭代写法对称二叉树的迭代写法不用栈而是用队列成对取出节点。核心思想是我每次往队列里推入两个“应该互为镜像”的节点然后取出来比较再把它们的下一层对应节点按正确的配对顺序推入队列。class Solution { public: bool isSymmetric(TreeNode* root) { if (root nullptr) return true; queueTreeNode* que; que.push(root-left); que.push(root-right); while (!que.empty()) { TreeNode* leftNode que.front(); que.pop(); TreeNode* rightNode que.front(); que.pop(); // 两个都为空当前对应位置对称继续下一对 if (leftNode nullptr rightNode nullptr) continue; // 一个为空或值不等直接判 false if (leftNode nullptr || rightNode nullptr || leftNode-val ! rightNode-val) { return false; } // 配对推入外侧一对内侧一对 que.push(leftNode-left); que.push(rightNode-right); que.push(leftNode-right); que.push(rightNode-left); } return true; } };队列里的节点永远是“两两一组”每次循环处理一组。顺序不能错先推外侧左的左 和 右的右再推内侧左的右 和 右的左。如果把推入顺序搞混了比较的配对就会错位明明对称的树也会被判成 false。建议自己模拟几组数据再上机跑。4. 111. 二叉树的最小深度最容易想当然的边界题4.1 最大深度都会写最小深度却容易翻车二叉树的最大深度人人都会写经典的递归一行int maxDepth(TreeNode* root) { if (root nullptr) return 0; return max(maxDepth(root-left), maxDepth(root-right)) 1; }于是很多人想当然地认为最小深度就是把 max 换成 minint minDepth(TreeNode* root) { if (root nullptr) return 0; return min(minDepth(root-left), minDepth(root-right)) 1; }这个写法在满二叉树每个节点都有左右孩子上是正确的但一旦遇到单分支节点就崩了。我先解释一下为什么会崩再给你正确的解法。4.2 错误写法复盘直接取 min 为什么翻车最小深度的定义是从根节点到最近的叶子节点的最短路径上的节点数。叶子节点的定义是“左右孩子都为空”。关键就在这如果一个节点只有左孩子没有右孩子那右子树传来的结果是 0——但是空子树并不是叶子节点它不构成一条有效路径。拿一棵只有左链的树举例1 / 2 / 3正确的最小深度应该是 3路径是 1 - 2 - 3。但如果用错误写法节点 3min(0, 0) 1 1正确。节点 2min(minDepth(3) 1, minDepth(右空) 0) 1 1错误这里右子树是空的不能参与比较但错误写法把 0 当成有效值直接导致节点 2 的最小深度被算成 1。节点 1min(minDepth(2) 1, 0) 1 1整个树的最小深度变成了 1。问题根源就是空子树不应该作为“比较项”参与 min 运算。只有当节点的左右孩子都为空时这个节点才算叶子才能返回深度。4.3 正确递归的三种等价写法正确思路是要区分三种情况当前节点是叶子返回 1。当前节点只有左孩子只在左子树里继续找最小深度右子树忽略。当前节点只有右孩子只在右子树里继续找最小深度左子树忽略。当前节点左右孩子都有两边都找取较小值加 1。写法一先判断叶子再分情况递归class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; // 叶子节点 if (root-left nullptr root-right nullptr) return 1; // 只有一个子树的情况 if (root-left nullptr) return minDepth(root-right) 1; if (root-right nullptr) return minDepth(root-left) 1; // 左右都有取较小值 return min(minDepth(root-left), minDepth(root-right)) 1; } };写法二单层逻辑上显式过滤掉空子树class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; int depth INT_MAX; if (root-left) { depth min(depth, minDepth(root-left)); } if (root-right) { depth min(depth, minDepth(root-right)); } // 如果 depth 没被更新说明当前是叶子节点返回 1 return depth INT_MAX ? 1 : depth 1; } };写法三在返回值进入下一层之前就把单分支情况消掉class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; int leftDepth minDepth(root-left); int rightDepth minDepth(root-right); // 若左子树为空右子树不空说明最小深度在右子树 if (root-left nullptr root-right ! nullptr) { return rightDepth 1; } // 若右子树为空左子树不空说明最小深度在左子树 if (root-left ! nullptr root-right nullptr) { return leftDepth 1; } return min(leftDepth, rightDepth) 1; } };三种写法本质相同。推荐第一种因为它把分支条件写得最直白面试时给面试官讲思路也最顺。记住一个口诀最小深度不是简单的 min1而是“有且只有一条子树时要沿着那条继续走”。4.4 BFS 是最省事的方案最小深度这道题如果允许迭代其实 BFS 是最优解。BFS 按层遍历第一次遇到叶子节点时返回当前层数这就是最小深度。因为是逐层扩展找到的第一个叶子一定位于最短路径上时间复杂度 O(n)但通常不需要遍历整棵树。class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; queueTreeNode* que; que.push(root); int depth 0; while (!que.empty()) { depth; int size que.size(); for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (node-left nullptr node-right nullptr) { return depth; } if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return depth; } };这题的教训很深刻递归的逻辑不难但你对边界条件的敏感度决定能不能一次写对。我见过太多人在面试里把 min 版本写出来被面试官提醒后才恍然大悟。刷题时一定要培养“空子树不能参与路径比较”这种边界意识。5. 训练营实操中的常见错误与排查思路5.1 LeetCode 报“运行时错误”到底怎么回事很多人在代码随想录训练营刷二叉树时提交后遇到 System.Runtime.Serialization 或者 RunTime Error第一时间很慌。我总结下来二叉树题目的运行时错误基本就三类空指针解引用最常见。访问了node-val或node-left但node为 null。多半是递归终止条件不完整或者某个分支忘了判空。栈溢出Stack Overflow递归深度过大。二叉树退化成长链时递归深度等于节点数 n如果 n 很大栈空间撑不住。LeetCode 上有些题的测试用例会故意构造很深的树这时候要考虑迭代法。死循环常见于迭代法里节点重复入队一般和队列操作逻辑有关。先说排查优先级先看错误行号定位崩溃的位置十有八九是空指针保护没写全。如果错误信息是栈溢出就检查终止条件是不是漏了或者递归前没有处理退化情况。5.2 递归调试三板斧递归题不像普通循环打印调试没那么直观。我自己的调试方法就三招实测下来很管用。第一招打印递归入口和出口。在递归函数开头打印当前节点值在 return 之前打印返回值。这样你能看到整个递归调用的轨迹。举个例子int minDepth(TreeNode* root) { if (root nullptr) return 0; cout enter: root-val endl; int ans ...; cout exit: root-val - ans endl; return ans; }第二招用小样本手动走。不要用大树的测试用例自己构造 2 到 4 个节点的树在纸上画出递归树逐层展开。像 226 翻转二叉树的中序错误代码一眼看上去是没问题的但只要手推两层就会露馅。第三招把返回值打出来对比。尤其是 111 最小深度这种边界权重的题打印每个节点的 leftDepth 和 rightDepth你能立刻看到空子树被错误地当成 0 参与比较。5.3 边界条件速查表练这三道题时我建议每次提交前都对照这个表自查一遍检查点翻转二叉树 226对称二叉树 101最小深度 111空树root 为 null返回 null 即可返回 true返回 0只有根节点返回根节点本身返回 true返回 1根节点只有一个孩子正常交换一定不对称返回 false向非空子树方向寻找两个节点互为镜像不适用判断值相等且外侧内侧一致不适用深链退化树栈深度等于节点数考虑迭代递归深同样小心BFS 更稳这道速查表的背后其实是一条通用规则写递归前先想清楚空树、单节点、单分支三种结构代码写完立刻用这三个用例过一遍。能抵抗 90% 的边界错误。在训练营里练题本质上是练一套可迁移的思维方式。第十二天这三道题让我感受最深的不是“我会写递归了”而是“我知道递归在什么情况下会失控”。递归不是背诵模板它是对“问题规模缩小”的建模。226 告诉你最小规模的单元是一个节点101 告诉你比较的最小单元是一对节点111 告诉你返回值的计算必须尊重树的真实结构。这三道题吃透后面遇到任何二叉树递归题你都多了一分“我先想边界再写逻辑”的底气。