今天是训练营打卡第16天二叉树这个大专题终于推进到part04。前三个part把递归遍历、迭代遍历、层序套路、翻转、对称、最大最小深度这些内容轮了一遍刷题手感已经慢慢热起来。但到了part04我明显感觉到难度开始换挡题目不再只是让你遍历一棵树或者改几个节点而是要求你在递归过程中做状态判断、拼接路径、收集特定节点难度一下子从“会不会写递归”跳到了“知不知道递归在每一层到底发生了什么”。今天这个part里我挑三道最有代表性的题来拆平衡二叉树判断、二叉树的所有路径、左叶子之和。这三道题一个比一个刁钻但串在一起看恰好对应了树形递归里最核心的三个能力用返回值传递状态、用回溯恢复现场、用边界条件兜住特例。把这三道题啃透后面那些路径总和、找左下角值之类的问题都会顺很多。想直接看干货的同学建议自带笔和纸因为今天涉及的概念比较多一边看一边在草稿纸上画递归状态比单纯盯着代码效率高得多。1. 今日题单与整体学习思路1.1 二叉树part04在训练营里是什么位置代码随想录的训练营把二叉树拆得非常细part01到part03解决的是“树的基本功”各种遍历顺序、迭代写法、层序变种、翻转、对称、深度统计。到了part04基础遍历已经默认你掌握了开始正式进入利用递归结构做逻辑判断的阶段。如果把二叉树的知识比作盖楼前几个part是在搭脚手架part04是在浇筑承重墙。今天涉及的题目不再有“标准答案式”的遍历模板每道题都需要你根据自己的需求设计递归函数返回值是int还是bool要不要回溯终止条件是node为空还是node为叶子这些选择直接决定代码是半小时写不出来还是五分钟一把过。我个人建议今天开始刷题前先别急着打开编辑器先拿出3分钟把每道题的递归三要素写下来参数、返回值、终止条件。想清楚再动手效率会高很多。1.2 三道题的知识点映射题目核心考点思路关键词最容易翻车的地方平衡二叉树递归状态传递、后序遍历高度、-1剪枝、左右子树联动把深度和高度混为一谈二叉树的所有路径回溯、路径收集叶子终止、恢复现场、引用传递在空节点处终止导致重复加载左叶子之和边界条件、父子节点关系父节点视角判断、叶子判定漏掉单支树和空树特例这三道题放在一起不是没有理由的。平衡二叉树逼你把“当前树合不合法”和“当前树有多高”打包在一起返回所有路径逼你在递归过程中维护一个会变化的路径容器左叶子之和逼你跳出“只看当前节点”的惯性从父节点视角往下看两层。三题互补性很强刷完能明显感觉到自己对递归函数的掌控力上升一截。1.3 为什么说part04是“递归分水岭”很多人刷二叉树前几个part时其实是在套模板先序遍历就是先处理根、再左右递归层序遍历就是用队列循环。到了part04模板开始失效因为每道题的递归函数都要“定制化”。比如平衡二叉树你不能简单套一个求深度的模板然后额外写判断——那样会重复遍历很多次。所有路径题如果你只会遍历不会回溯路径列表里就会残留已经访问过的节点。左叶子之和如果你只会判断“当前节点是叶子”那永远算不对因为左叶子必须从父节点那里才能定义。这个阶段本质上是在训练一种能力把问题的判断条件映射到递归的返回值、参数和终止条件上。一旦过了这道坎后面二叉搜索树、公共祖先、序列化等难题都不会觉得无从下手。2. 平衡二叉树判断递归怎么同时返回“高度”和“是否平衡”2.1 先分清高度和深度不然代码必崩平衡二叉树的定义很直接每个节点的左右子树高度差不超过1。我看到不少同学看到这题就开始写“求最大深度然后比较左右深度差”结果深度和高度混着用代码结构一塌糊涂。深度是从根节点往下数根节点深度是0或者1高度是从叶子节点往上数叶子节点高度是0或者1。判断平衡树的时候我们关心的是“左右子树谁更长、差多少”所以计算的是高度。你可以在定义里用你自己的约定但代码里必须自洽。大多数递归解法里叶子高度返回1空节点返回0这样父节点高度就是左右子树高度较大值加1。如果你从根节点开始往下数深度再返回来判断平衡逻辑会绕很多而且很难处理空节点。我建议统一采用“叶子高度1、空节点高度0”的约定。2.2 为什么必须用后序遍历上面这一段是标题里的## 2. 平衡二叉树判断递归怎么同时返回“高度”和“是否平衡”下面继续展开。判断一棵树是否平衡你得先知道左右子树各自的高度再回到当前节点做差值判断。这个过程天然就是“先左、再右、最后根”的后序遍历。前序和中序都做不到因为访问根的时候子树信息还没有收集回来。很多第一次写的同学会写成这样在主函数里对每个节点都调用一次求深度函数然后在外面比较左右深度。这能过但问题很大——每到一个节点都会把它的整棵子树重新遍历一遍复杂度接近O(n^2)树一深就明显卡顿。正确的做法是在一次后序遍历里同时干两件事算高度、判平衡。提示判断平衡树的代码最终要的不是“这棵树高度多少”而是“这棵树是否平衡”。所以递归返回值的语义要想清楚。2.3 返回值设计的经典方案用-1标记不平衡这道题最漂亮的设计是让递归函数返回int子树平衡时返回该子树的高度不平衡时返回-1。这样上一层调用时只要看到-1就知道下面的子树已经不平衡了可以直接剪枝不需要继续遍历剩下的部分。这个“用特殊返回值标记异常状态”的思路在很多树形判断里都能复用。比如判断二叉树是否对称、是否同一棵树都可以用类似方式在返回bool的同时携带关键信息。代码我用C写了一个标准版本放下面。int getHeight(TreeNode* node) { if (node nullptr) { return 0; } int leftHeight getHeight(node-left); if (leftHeight -1) { return -1; // 左子树已经不平衡直接返回 } int rightHeight getHeight(node-right); if (rightHeight -1) { return -1; // 右子树已经不平衡直接返回 } if (abs(leftHeight - rightHeight) 1) { return -1; // 当前节点发现不平衡 } return max(leftHeight, rightHeight) 1; } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; }这里有一个细节值得反复体会leftHeight -1这个判断必须在继续递归右子树之前完成。这样只要某个子树一旦发现不平衡整棵树的递归就会快速终止不会做无用功。这个剪枝的效果在极端不平衡的树比如一条链式的树上特别明显。2.4 常见误解只返回bool到底行不行有同学看完题会问我直接返回bool表示是否平衡不行吗当然可以但如果你只返回bool上层节点就拿不到子树高度无法判断差值是否大于1。这时候只能额外传引用参数记录高度代码可读性和稳定性都会下降。我当时写的时候也试过用pairbool, int来返回“是否平衡高度”这个思路没问题但写起来比-1标记要啰嗦一些而且在剪枝判断时容易漏改某个返回值。相比之下返回int并用-1作为哨兵值代码最简洁也不容易出错。平衡树这道题写完之后我总结了一个判断标准你的递归函数能否在O(n)时间内完成所有判断如果写出来的代码反复调用了求深度函数多半是要重构的。力扣上这道题的题号是110大家可以拿它对比自己的解法复杂度。3. 二叉树的所有路径回溯的第一次强烈感知3.1 题目到底要你做什么所有路径这道题要求收集从根节点到每一个叶子节点的完整路径输出成字符串列表。核心对象是二叉树但考察重点其实在于回溯你要在递归进入左子树和右子树时维护一个不断变化的路径容器。这道题是我在part04里卡得比较久的题不是因为思路难想而是因为一开始我用字符串直接拼接忽略了一个问题同一个节点会被多个路径共享。你往左走时向路径里加了节点回到上一层往右走时如果不把左分支的节点移出去路径就会越攒越长最后输出的每条路径都带着其他分支的“残留”。回溯翻译成人话就是递归进入孩子之前往路径里加入当前节点递归返回之后把当前节点从路径里移除。走哪条路就把那条路上的节点保留下来不走的路就该清干净。3.2 终止条件用“叶子节点”而不是“空节点”这道题另一个关键点是终止条件。常规递归习惯是node nullptr就返回但在这里会出现问题当一个节点只有左孩子没有右孩子时空节点返回会让右分支也执行逻辑或者在添加路径时把空节点处理错。标准写法是把终止条件设在叶子节点node-left nullptr node-right nullptr。到叶子时直接把当前路径转成字符串存进结果里。这样每次递归只发生在有孩子的时候不会出现对空节点“空处理”的尴尬局面。很多同学会问不在空节点返回那递归函数怎么保证不越界其实只要调用前判断孩子是否为空即可有左孩子才递归左孩子有右孩子才递归右孩子。这样空节点根本不会被进入代码反而更直观。3.3 完整代码vector存路径 回溯恢复现场C写法我放在下面重点看path.pop_back()的位置。void traversal(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); // 到达叶子节点生成路径字符串 if (node-left nullptr node-right nullptr) { string s; for (int i 0; i path.size() - 1; i) { s to_string(path[i]); s -; } s to_string(path[path.size() - 1]); result.push_back(s); return; } if (node-left) { traversal(node-left, path, result); path.pop_back(); // 回溯恢复进入左子树之前的状态 } if (node-right) { traversal(node-right, path, result); path.pop_back(); // 回溯恢复进入右子树之前的状态 } } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root nullptr) { return result; } vectorint path; traversal(root, path, result); return result; }注意path.pop_back()必须紧跟在递归调用之后不能提前也不能漏掉。提前pop会把当前节点的其他孩子路径破坏掉漏掉pop路径里就会积累已经遍历过的其他分支节点。当时我第一次写的时候把path.pop_back()放在了if (node-left)外面结果左分支遍历完回上一层后右分支路径里还带着左分支的尾部节点输出的路径全是错的。后来我在纸上模拟了一遍递归过程才发现问题出在“回溯的位置必须和递归的位置一一对应”。3.4 小优化用传值的方式代替显式回溯有一个偷懒技巧在递归函数参数里直接传一个按值传递的vectorint path这样每次递归都会复制一份新的路径天然不需要回溯。代码可以少写几个pop_back但代价是每一层递归都复制整个数组复杂度不够漂亮。我建议初学者先用回溯法把恢复现场的动作写清楚。等理解了回溯的本质再尝试传值写法也不迟。面试时写回溯版更显功底因为面试官就是想看你对现场状态的控制力。这道题的输出格式是字符串拼接所以C里to_string最省事。如果你用其他语言也要注意路径分隔符的一致性常见的是-别写成-或者--。3.5 回溯和递归的关系别把它当成玄学我学这道题的最大收获是回溯不是递归之外的神秘操作它只是递归调用的自然要求。递归的执行过程像一条深度优先的路径进入左子树前路径上的状态是A从左边返回后状态应该仍然恢复到A才能干净地进入右子树。只要把递归想象成“带着一个背包深度遍历”回溯就是“从背包里拿出之前放进去的东西”。二叉树的所有路径这道题本质上是让你手动管理这个背包。一旦想明白这个点后面遇到组合总和、全排列、子集等回溯问题你会有一种豁然开朗的感觉。4. 左叶子之和把边界条件抠到极致4.1 左叶子的定义到底是什么左叶子之和这道题题目描述特别短返回所有左叶子节点的值之和。但“左叶子”三个字里藏着两个限制条件第一个这个节点必须是一个叶子节点也就是没有左右孩子第二个这个节点必须是它父节点的左孩子。这两个条件叠加起来导致一个简单的误区你无法在当前节点自身判断它是不是“左叶子”。因为任何一个节点只能知道自己是不是叶子、自己的值是多少但“它是不是父节点的左孩子”这个信息存在父子和它的关系里不是当前节点的属性。所以这道题的遍历视角必须从父节点出发我有没有左孩子这个左孩子是不是叶子如果是我就把它记进结果里。用代码写出来就是if (node-left !node-left-left !node-left-right)。4.2 为什么用前中后序都能做这道题不像平衡二叉树那样必须后序因为判断左叶子只需要父节点和孩子节点的信息不需要从子树内部返回汇总数据。理论上前序、中序、后序都可以只要你保证每个节点都被访问到。我自己习惯用后序因为可以把求和逻辑和遍历逻辑统一放在递归返回时处理代码看起来更整齐。但也有人喜欢用前序到父节点就立刻判断左叶子然后累加。这两种写法都能AC选哪种看个人习惯。空节点处理也要注意如果root为空直接返回0如果root本身是叶子它既不是左叶子也不是右叶子所以返回0。很多同学漏了“单节点树返回0”这个特判导致结果比期望多出一个根节点的值。4.3 递归版和迭代版代码递归版代码如下int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) { return 0; } int sum 0; // 判断当前节点的左孩子是不是左叶子 if (root-left root-left-left nullptr root-left-right nullptr) { sum root-left-val; } // 分别收集左右子树中的左叶子 sum sumOfLeftLeaves(root-left); sum sumOfLeftLeaves(root-right); return sum; }我试过用层序迭代法用栈或队列遍历每个节点每弹出一个节点就按上面的if判断它的左孩子是否为左叶子。这个方法比递归更直观适合不习惯递归的同学。核心判断条件完全一样只是遍历容器从系统调用栈换成了显式栈。注意判断左叶子用的是node-left-left和node-left-right这两个访问必须建立在node-left不为空的基础上。写条件顺序时一定要把root-left的判空放在前面避免空指针访问。4.4 容易被忽略的边界情形写这道题时最好自己跑一遍这三种边界树空树、只有一个根节点、根节点只有右孩子。空树返回0单节点返回0只有右孩子时根节点没有左孩子左叶子之和当然也是0。如果代码在这三种输入下都输出0基本说明边界处理没问题。还有一个更隐蔽的坑左叶子可能存在在右子树的左分支里。比如根节点只有右孩子但这个右孩子的左孩子是叶子那这个“左叶子”其实是在右子树里的节点。递归版代码天然能处理这种情况因为你对左右子树都做了递归搜索。我见过一个错误写法只在根节点判断一次左叶子就结束结果只计算了根节点的左叶子漏掉更深层次的所有左叶子。这道题不要被“左”字迷惑它要求的是全树范围内、所有“作为左孩子的叶子节点”的值之和。5. 今日踩坑与排查实录5.1 坑一递归结果没有接住刷平衡二叉树的时候我第一次写的是if (abs(getHeight(root-left) - getHeight(root-right)) 1) return false;这段代码看着没毛病但问题在于这个判断只执行在根节点并没有递归到每个子节点。判断一棵树是否平衡必须每个节点都满足条件。后面改成在getHeight内部就判返回-1才真正覆盖到所有子树。这类错误的排查思路很有通用性当你发现某个树形判断只检查了根节点说明递归函数的返回结果没有被上层“接住并继续传递”。检查时重点看递归函数内部是否使用了子问题的返回值来判断当前节点。5.2 坑二回溯写在了错误的位置所有路径题里我最开始把path.pop_back()放在if (node-left)的外面执行顺序变成了“递归左孩子、弹出、递归右孩子”这样左孩子递归时弹出的路径会影响正在构建的路径。正确的顺序是“递归左孩子、从路径弹出左孩子加进去的节点、递归右孩子、从路径弹出右孩子加进去的节点”。排查这类问题时我推荐一个小技巧在递归函数开头打印path的内容。如果进入左子树和进入右子树前打印出的path不一样说明回溯没有把路径恢复原样。路径恢复不了后面拼出来的字符串就全是脏数据。5.3 坑三空指针异常左叶子之和里判断条件如果写成if (root-left-left nullptr)而没有先判断root-left是否为空在单支树或空节点上会直接崩溃。C里空指针访问是运行时严重错误刷题平台的报错往往是“段错误”而不是明显提示。我的自查习惯是每次代码里出现连续两次-都停下来问自己前一个指针有没有可能为空。如果有可能就一定要在前面加判空。这是一个看似基础但极其关键的工程意识工作中写业务代码也同样适用。5.4 调试技巧小树手推 打印递归状态今天的几道题我都推荐一个调试手法拿一个只有3到5个节点的小树在纸上画出递归调用的轨迹把每次进入函数时path或hight的值写下来跟代码执行结果对比。在代码里临时加打印也可以C里用cout 在返回前输出当前节点的值和路径状态。注意刷题提交时要把打印删掉不然输出格式会被污染提交全部报错。我一般会先本地跑用例看打印确认没问题后再注释掉输出语句提交。5.5 快速排查对照表现象可能原因修改方向平衡判断总在根节点出问题递归返回值没被传递和判断确保左/右递归返回-1时立即返回-1路径里出现其他分支节点回溯的pop位置不对或缺失保证每个递归调用后只弹出一个节点左叶子之和缺少深层节点只在根节点判断左叶子对整个左/右子树递归计算报错“段错误”连续解引用空指针增加判空或调整条件顺序6. 刷完今天的题我发现可以这样复盘6.1 提炼三个可复用的递归模板今天的三道题我分别提炼出一个模板后面刷题可以直接套。状态判断模板返回值除了正常数值额外用一个特殊值表示“状态不成立”比如平衡二叉树里的-1。这样一次遍历就能完成计算和校验复杂度保持在O(n)。路径收集模板用引用传容器进入递归前放入当前节点递归返回后弹出当前节点。终止条件设在满足输出目标的位置比如叶子节点而不是空节点。边界细查模板遇到“根据父子关系才能判断”的题目把判断逻辑放在父节点位置并且把连续解引用前的判空写清楚。递归逻辑往往很简单坑都在空指针和单分支上。这三个模板覆盖的题型非常广。状态判断可以引申到判断对称、判断相同的树路径收集可以引申到路径总和、求根到叶数字之和边界细查可以引申到统计叶子节点、收集特定子树等。建议把模板记到自己的笔记里刷题时直接套。6.2 后续会遇到的同源题目训练营后面的二叉树题目里很多都是今天这三道题方法的组合扩展。比如路径总和这道题是“所有路径”的简化版不需要收集所有路径只需要判断从根到叶是否存在一条和为target的路。你可以用回溯路径的方式但不需要维护完整字符串只需要累加节点值再回溯差值。找树左下角的值这道题本质是在所有路径基础上找到最后一行最左边的叶子。如果你已经掌握了层序遍历或者带层数的递归这道题会很快解决。再往后遇到的二叉搜索树相关题目很多也用到了“用返回值传递状态”的思想比如验证是否为二叉搜索树时你需要在遍历中传递当前子树的最小值和最大值边界。今天的平衡二叉树就是一次很好的预演。6.3 对实际能力的影响不只是刷题说点实际的练到这一part递归的理解深度会直接影响你后续的编程能力。很多生产环境里的代码——比如解析JSON、遍历文件目录、渲染树形组件——本质上都是树形递归。如果你能一眼看出递归函数的返回值和回溯点写这类业务代码的效率会高非常多。我在实际工作中写过一次目录树的操作脚本核心逻辑就是“递归进入每个子目录处理完再回到当前目录”。当时我脑海里直接浮现的就是今天所有路径这道题的回溯结构。所以说训练营刷题不只是为了面试也是在构建解决真实问题的底层思维。6.4 给一起打卡的同学一点经验如果你今天也卡在某些题上我的建议是不要死磕一道题超过40分钟。刷题过程中卡住很正常先看题解理解思路再关上题解自己写一遍效果远比死磕两小时体感好。写不出来就抄但抄完必须合上答案自己复现复现不出来就该重看。每一道题至少做三遍第一遍看懂思路第二遍独立写出代码第三遍在几天后再写一次。我在训练营里最大的体会是当天觉得会的题一周后大概率忘了一半。所以标记好哪些题需要二刷是保持长期记忆的最好方式。我个人还会在每天的笔记里写上一句话记录这道题“最想让人忘记的坑”。比如今天的三道题我会写平衡树记得用-1剪枝路径记得pop_back左叶子记得从父节点看孩子。有了这句话下次复习时扫一眼就能想起整道题的精髓。7. 最后再分享一个我自己的小技巧刷完今天的题我在复盘时发现一个特别实用的习惯把每道题的递归函数画成“子问题替换图”。什么叫子问题替换平衡二叉树这道题getHeight(root)做的事情是先求左子树高度再求右子树高度然后看差值最后得到整棵树高度。你在纸上把getHeight(root)替换成它的执行步骤就能直观看到后序遍历的调用链。路径题里把traversal(root, path)替换成“往path里加root的值、递归左孩子、把值弹出、递归右孩子、把值弹出”就能理解为什么回溯顺序和递归顺序一一对应。这个方法练习几次后你会发现再看递归题脑子里会自动展开调用轨迹不再是一个黑盒。DAY16的二叉树part04说到底就是在训练你把“黑盒递归”变成“透明递归”。能看清每一层做什么、返回什么、修改什么树形算法的基本功就算真正过关了。接下来不管遇到翻转、路径还是搜索树都只是在这个基础上的场景扩展。