1. 刷题前的思路整理这四个题到底在考什么代码训练营走到D15二叉树相关的题目开始从“会遍历”进阶到“会用遍历结果做判断、做路径记录、做条件求和”。今天这四道题——110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和、222. 完全二叉树的节点个数放在一起刷是非常合理的因为它们本质上都是在考察递归遍历过程中“如何携带信息、如何提前返回、如何通过返回值向上传递状态”。先说一个很多人刷二叉树时共通的困惑为什么递归代码看着逻辑没错一提交就报运行时错误我自己的经验是绝大多数问题出在“没有想清楚递归的终止条件”和“递归返回值在每一层到底代表什么”这两件事上。今天这四道题恰恰把这两个问题翻来覆去地考了个遍。先说适用人群这一组题目对刚学完二叉树遍历、正准备接触递归进阶应用的读者来说非常合适。四道题难度都不大但每道题都代表了一种递归设计模式刷完之后你对“返回值型递归”和“路径型递归”的理解会上一个台阶。2. 110. 平衡二叉树递归返回值的经典示范2.1 题目到底在问什么平衡二叉树的定义在LeetCode上是这样一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。注意是“每个节点”不是只检查根节点。这句话是这道题最大的坑。我见过很多初学的朋友写代码时只看根节点左右子树的高度差一跑示例就过了提交就挂。原因很简单根节点平衡不代表子树平衡。比如一棵树根节点左右子树高度差为0但左子树的某个孙节点左右高度差已经是3了这棵树依然不是平衡二叉树。2.2 递归设计的核心思路这道题标准的解法是“后序遍历 高度差判断”递归函数返回的是“以当前节点为根的子树的高度”但是在计算高度的过程中一旦发现左右子树高度差超过1就立刻返回一个特殊值常用-1来表示“这棵树已经不合法了”。这里我需要重点解释一下为什么用-1做标记。高度本身一定是非负整数叶子节点高度可以定义为0或1不管哪种定义-1都不会和合法高度冲突。用-1标记异常状态可以避免额外定义一个全局变量或者布尔标记让递归函数同时完成“算高度”和“查平衡”两件事代码会干净很多。递归每一步的逻辑是递归算左子树高度如果返回-1说明左子树已经不平衡直接返回-1。递归算右子树高度如果返回-1直接返回-1。计算左右子树高度差如果绝对值大于1返回-1。否则返回当前节点高度即左右子树较大高度加1。2.3 代码实现与逐行解读C写法class Solution { public: 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; } };这段代码有几个细节值得单独拎出来讲。第一个细节是叶子节点的高度。这里空节点返回0叶子节点的高度就是max(0, 0) 1 1你要习惯这种定义后面很多题都会沿用。第二个细节是剪枝时机。左子树一旦返回-1就马上return -1不再去递归右子树。这相当于一个短路判断虽然是递归但异常情况下的递归路径会被提前掐断后续无用功全部跳过。第三个细节是主函数极其简单只判断返回值是否为-1。这就是“返回值型递归”的典型特点所有判断逻辑都藏在递归函数内部主函数只关心最终结果。2.4 为什么说这道题是“后序遍历的实战课”后序遍历的特点是“先处理孩子再处理自己”天然适合需要孩子节点提供信息给自己做判断的场景。平衡二叉树要判断当前节点是否平衡必须先知道左右子树的高度差所以必须用后序。对比前序遍历写这道题会非常别扭你还没走到孩子节点就先判断当前节点是否平衡可此时孩子高度未知只能再用额外函数去查高度导致大量重复遍历时间复杂度基本退化到接近O(n²)。这也是为什么很多人在面试中写这道题时被追问“你这是一个递归里套递归吧能优化吗”的原因。2.5 实操心得从-1到“布尔值高度”的设计取舍我刷这道题时踩过一个坑。早期版本里我用了引用类型的布尔变量bool isBalanced然后在递归里不断修正它的值最后主函数返回这个布尔变量。写法上没问题但代码的可读性和可迁移性差不少——你一旦想复用这个“算高度”的逻辑引用参数就成了累赘。改用-1标记之后递归函数变得独立、无副作用随时可以拿出来单独测试。这也是我想提醒大家的一点递归函数的签名设计决定了代码的“可测试性”和“复用性”。尽量让递归函数只通过返回值和外部交互不要依赖外部变量去记录中间状态除非这个状态本身就是题目想要的结果比如路径记录。3. 257. 二叉树的所有路径递归中的路径传递3.1 题目的本质是“记录旅程”这道题要求返回所有从根节点到叶子节点的路径格式类似于1-2-5。猛一看和遍历差不多实际上它是一个“从上到下传递路径”的过程。你需要理解路径类题目的本质是父节点把自己累积的路径片段交给子节点子节点在它的基础上继续追加当到达叶子节点时把完整路径输出。这和你平时递归只向上返回结果不太一样它需要的是“向下传递”配合“到达终点时结算”。3.2 递归 回溯为什么必须回溯这道题最经典的写法是递归加回溯。核心逻辑是这样的class Solution { public: void traversal(TreeNode* cur, string path, vectorstring result) { if (cur nullptr) return; if (cur-left nullptr cur-right nullptr) { result.push_back(path to_string(cur-val)); return; } traversal(cur-left, path to_string(cur-val) -, result); traversal(cur-right, path to_string(cur-val) -, result); } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; string path; if (root nullptr) return result; traversal(root, path, result); return result; } };注意这里我用的是按值传递的path每次递归调用时生成新字符串天然实现了回溯——上一层的path永远不会被下一层的操作污染。但很多教材和面试题的标准解法会用引用传递加回溯操作大致是void traversal(TreeNode* cur, string path, vectorstring result) { if (cur nullptr) return; path to_string(cur-val); if (cur-left nullptr cur-right nullptr) { result.push_back(path); return; } path -; traversal(cur-left, path, result); traversal(cur-right, path, result); path.pop_back(); // 回溯去掉箭头 // 还要考虑去掉数字的多位问题其实并不好处理 }这种写法里字符串的回溯非常麻烦因为你要面对1-2-这样的字符串pop_back只能去掉箭头末尾的-却没法干净地去掉数字。如果节点值是两位数、三位数回溯计算的复杂度让人头大。所以我的建议是在刷题阶段优先选择“值传递 新字符串拼接”简化回溯过程。等理解透了再去看看引用传递版本是如何实现精确回溯的这也能帮你建立对回溯算法更深刻的理解。3.3 路径与markdown图片路径的类比理解顺便说个题外话热词里有一条markdown图片路径和这道题放在一起看很有意思。写博客的时候图片路径经常出现../../assets/xxx.png这种写法它本质上就是一个从根目录到目标文件的路径记录中间每个..都是向上回溯。和二叉树路径题一样你维护的是一个累积路径每进入一层目录就拼接一段出目录就回退一段。多想想这种类比你会发现算法题其实就在我们常用的工具里。3.4 边界与空树处理这道题有一个容易忽略的边界根节点本身就是空节点时返回的应该是空数组而不是包含空字符串的数组。代码里用if (root nullptr) return result;处理掉了。还有一个容易被测试用例教育的地方如果树只有根节点没有左右孩子那么根节点本身就是叶子应该返回根节点值这样一条路径。这个逻辑在traversal里的叶子判断条件中天然覆盖了不需要额外写特殊情况但如果理解不到位可能会在路径结尾处多拼一个null之类的字符串这种错误属于典型的运行时逻辑错误不报编译错但一提交就失败。4. 404. 左叶子之和停止无脑递归的边界判断4.1 左叶子的精确定义“左叶子”指的是某个节点如果有左孩子且这个左孩子没有任何孩子节点即它是叶子节点那么这个左孩子就是“左叶子”。这里最容易被带偏的地方在于——判断一个节点是不是左叶子遍历视角不同写法完全不同。我见过很多朋友试图在递归到自己时判断“我是不是左叶子”这其实做不到因为你无法得知自己对于父节点来说是左孩子还是右孩子。需要把“判断”放在父节点这一层。换句话说当你遍历到某个节点A时你要不要检查A的左孩子是不是左叶子要。怎么检查A-left ! nullptr A-left-left nullptr A-left-right nullptr。4.2 递归设计先判断再做累加class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; int sum 0; if (root-left ! nullptr root-left-left nullptr root-left-right nullptr) { sum root-left-val; } return sum sumOfLeftLeaves(root-left) sumOfLeftLeaves(root-right); } };这段代码的巧妙之处在于它对当前节点的左孩子进行了“左叶子判定”如果没有左孩子或者左孩子不是叶子那就不累加然后继续递归左右子树。整体采用的是前序遍历的顺序但也可以换成后序、层序只要判定逻辑正确结果都一样。4.3 常见错误与调试技巧这道题最常见的错误是在递归函数里写“如果当前节点是叶子且是左孩子才累加”但当前节点并不知道自己是左孩子。你可能会想到给递归函数加参数例如bool isLeft这当然可行int sumOfLeftLeaves(TreeNode* root, bool fromLeft) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr fromLeft) { return root-val; } return sumOfLeftLeaves(root-left, true) sumOfLeftLeaves(root-right, false); }这也是一种解法而且更直观。但要注意这里第一层调用时fromLeft需要传入false否则根节点如果是叶子会被错误地当成左叶子累加。这两种方案没有绝对优劣第一种判断更聚焦第二种思路更通用适合扩展到“右叶子之和”“偶数深度叶子之和”这类变体题。我建议初学者把两种方法都写一遍体会一下“父子关系建模”的区别。4.4 节点数量少时的极端情况还要提一个实际提交时容易翻车的细节如果树只有一个根节点且没有左右孩子它算不算左叶子不算。因为左叶子的定义首先要求它是某个节点的“左孩子”根节点没有父节点永远不满足“左”这个条件。这个边界在第一种写法中天然绕过了在第二种写法中靠第一层fromLeft false正确规避。5. 222. 完全二叉树的节点个数普通解法与专用解法的分水岭5.1 什么是完全二叉树完全二叉树的定义是除了最后一层外每一层都是满的最后一层的节点都尽量靠左排列。这个定义非常重要脱离这个定义去理解下面的优化算法是行不通的。5.2 通用解法遍历数一遍最简单的思路就是遍历整棵树把节点数出来任何遍历方式都可以class Solution { public: int countNodes(TreeNode* root) { if (root nullptr) return 0; return 1 countNodes(root-left) countNodes(root-right); } };这个解法对所有二叉树通用时间复杂度O(n)。这么写当然没问题但如果你只学到这一层就浪费了“完全二叉树”这个条件。5.3 利用满二叉树特性的优化解法完全二叉树有一个性质如果一个子树是满二叉树它的节点数量可以直接通过高度计算公式是2^h - 1其中h是子树的高度。判断某个子树是不是满二叉树在完全二叉树的约束下有一个非常简单的办法沿着这个子树的最左路径走到底记录高度h再沿着最右路径走到底记录高度h如果两者相等说明这是满二叉树。原因在于完全二叉树的形态决定了如果左右最深层级相同中间不可能缺节点。这个性质是普通二叉树不具备的。利用这个性质递归可以写成class Solution { public: int countNodes(TreeNode* root) { if (root nullptr) return 0; TreeNode* left root-left; TreeNode* right root-right; int leftHeight 0, rightHeight 0; while (left) { left left-left; leftHeight; } while (right) { right right-right; rightHeight; } if (leftHeight rightHeight) { return (2 leftHeight) - 1; // 注意左移运算 } return 1 countNodes(root-left) countNodes(root-right); } };这里需要特别说明的是2 leftHeight这个写法。如果子树高度为leftHeight 1满二叉树节点数为2^(leftHeight1) - 1。我们在代码里2 leftHeight等价于2 * 2^leftHeight 2^(leftHeight 1)然后再减1。这个细节如果你不仔细推敲容易把边界写错导致示例能过、大数据量下结果差1。5.4 复杂度分析与递归过程推演这个优化解法的时间复杂度是O(log²n)因为每次递归都会有一个顺着子树边缘走到最底层的循环循环次数和子树高度相关而完全二叉树的高度是O(log n)最多需要递归O(log n)层。所以总复杂度是O(log n × log n)。我建议你手动跑一个例子一棵完全二叉树根节点左右高度不同那么整体不算满递归进入左子树和右子树其中左子树可能直接是满二叉树套公式返回右子树也可能直接是满的整个递归过程其实非常短。你真正动手推演一遍之后才能体会这个算法“裁剪”的力量。5.5 与“根据错误码定位路径”这类排查思维的类比网上热词里有一条是“根据错误码定位路径的方法”我觉得和这题有异曲同工之妙。错误排查时你并不会逐行阅读所有日志而是利用错误码直接缩小排查范围命中率高且速度快。完全二叉树节点数计算也是如此利用满二叉树性质直接套公式避免遍历所有节点本质上都是“利用结构性信息做剪枝”。5.6 易混淆点满二叉树、完全二叉树与平衡二叉树这里顺便帮你理清三个概念很多人刷完这三题之后把它们混为一谈。类型定义最突出的性质完全二叉树最后一层允许不满但节点靠左排列可用数组顺序存储子树可能为满二叉树满二叉树所有层的节点数都是满的树形整齐节点数可由高度直接计算平衡二叉树任意节点的左右子树高度差不超过1是任意二叉树的一种性质不要求形状满这三者互不隶属。平衡二叉树可以是完全二叉树也可以不是满二叉树一定是完全二叉树但完全二叉树不一定是满的。这几道题放在同一天刷概念辨析就变得尤为重要。6. 四道题横向对比递归模式总结6.1 核心维度对比表把这四道题的核心特征放在一张表里训练效果会更好题目遍历顺序核心思想返回值语义关键易错点110. 平衡二叉树后序用-1标记异常剪枝提前返回返回子树高度或-1必须检查每个节点257. 二叉树的所有路径前序 回溯路径向下传递叶子节点结算无返回值结果收集在外部字符串拼接的回溯404. 左叶子之和前序/后序均可在父节点层判断左孩子返回子树内左叶子之和根节点的边界222. 完全二叉树的节点个数后序 满树剪枝满二叉树高度公式返回子树节点总数左移运算的边界6.2 为什么“递归返回值语义”是核心中的核心四道题里110和222主要依赖返回值向上一层传递信息257依赖参数向下传递信息404则是判断逻辑放在当前层、结果向上汇总。这三类模式对应的其实就是日常开发中常见的几种数据处理方式向上汇总型统计类需求比如工资汇总、库存盘点。向下累计型日志链路追踪父任务的上下文传给子任务。当前层判断型权限校验当前节点依据孩子状态做决策。理解递归不只是为了刷题这种“信息流向”的思考方式在系统设计和问题排查里到处都能用。6.3 一道变体题的现场拆解为了检验你今天的掌握程度我出一道变体求二叉树中所有右叶子之和限制条件与404完全相同。先自己默写代码再看下面的答案。class Solution { public: int sumOfRightLeaves(TreeNode* root) { if (root nullptr) return 0; int sum 0; if (root-right ! nullptr root-right-left nullptr root-right-right nullptr) { sum root-right-val; } return sum sumOfRightLeaves(root-left) sumOfRightLeaves(root-right); } };思路完全对称把left替换为right即可。如果你能在一分钟内完成转换说明你对这道题的递归边界已经真正掌握了。7. 刷题过程中的五个高频问题速查这部分是给实战中容易卡壳的朋友准备的速查表每一条都是我或我带过的学员实际上踩过的坑。7.1 为什么我的递归代码会出现运行时错误栈溢出、空指针运行时错误在二叉树递归里最常见的原因有三个递归终止条件不完整导致无限递归栈溢出。比如在257题中如果只判断cur nullptr而不判断叶子节点从根一路递归到空指针才会停下来路径记录的节点顺序就是错的。对空节点的成员变量访问越界。比如在404题里如果先写root-left-val而不先检查root-left是否为空空指针解引用必然报错。递归深度太深导致栈溢出这在极端退化的链状树上赋值1万层时就会发生。刷题平台数据一般不会大到让你栈溢出但自己本地测试时要注意。排查方法先在代码里加一个计数器递归进入时计数加1看看到底走了多少层。如果层数远远超过树的高度那必然是递归路径有循环或者终止条件缺失。7.2 为什么我的结果总是差一个边界节点差“一个节点”的问题绝大多数出在“根节点是否参与判断”或者“叶子节点的判断条件写反”上。以404题为例如果你在递归函数内部判断“当前节点是左叶子就累加”而不是在父节点层判断那么根节点如果是叶子会被误加如果根节点不是叶子又会漏掉根节点的左孩子是叶子的情况。无论哪种结果都和正确答案差一个节点。解决办法是写代码之前先在纸上画出这几种情况只有一个根节点根节点有一个左孩子且左孩子是叶子根节点有左孩子但左孩子不是叶子有左右孙节点跑通这三种边界结果就稳了一大半。7.3 为什么257题用引用传递时结果里出现重复路径这是回溯不彻底的典型表现。当你使用string path时每层递归对path的修改都会持久化。如果某个分支在返回后没有把path恢复原样下一个兄弟分支会基于错误的状态继续拼接导致路径内容重复或错位。解决办法直接用值传递或者在使用引用传递时务必精确回溯每一个追加的字符和箭头。真要执意用引用版建议把箭头拼接放在叶子判断之后简化pop_back的回溯操作。7.4 为什么222题的公式答案在个别用例上多1这个问题的根源是对“高度”的定义不一致。有人把空节点高度记为0叶子节点高度记为1那满二叉树节点数就是2^h - 1其中h是叶子到根的高度也有人把叶子高度记为0那节点数公式就要相应调整。这两种定义都会影响左移运算的位数。我的建议是统一采用“叶子高度1、空节点高度0”的定义并强制记忆一棵高为h的满二叉树节点数为2^h - 1。这样110题的高度计算和222题的节点数计算就能共用同一套体系。7.5 为什么LeetCode示例能过提交就超时典型场景是222题使用通用O(n)解法在极端大的完全二叉树上遇到超时。或者110题使用了“递归内再递归”的朴素判断法导致O(n²)复杂度。解决超时的核心思路就是利用题目给的特殊条件——完全二叉树就用满树公式剪枝平衡二叉树就用后序遍历一次算高度。不要总想着“通用解法够用”刷题的意义之一就是学会利用约束条件做优化。8. 今天这组题做完之后下一步该练什么这四道题覆盖了递归的三种信息传递模型向上返回、向下传递、当前层判断。如果你觉得消化得不够扎实我建议你先不急着往下推进而是做以下三件事。第一把110题的“-1标记法”和“布尔值标记法”各写一遍比较两种写法在代码可读性和异常剪枝上的差异。第二把257题改成输出所有根到叶子路径的节点值之和即每条路径上的节点值累加看看路径传递模型还能怎么变。第三自己造几个特殊的完全二叉树手工计算节点数再拿代码跑一遍验证左移运算的边界。按我多年的刷题经验二叉树这组题是典型的“今天练完觉得懂了一周后不复习又忘了”的类型。建议你把这四道题的题号记录在笔记里三天后重新默写一遍一周后再做一遍限时版。反复三轮递归的思路就会基本长在脑子里。到时候再去做更复杂的二叉树题目比如最近公共祖先、二叉搜索树相关题目会发现底子打得非常牢。最后分享一个我自己的小习惯每次刷完一组题我都会用一句话总结每道题的“题眼”。今天这四道题的题眼分别是110是“后序高度差检测”257是“值传递代替回溯”404是“父节点层判断子节点”222是“满树公式剪枝”。下次看到类似题目先想题眼再动手写代码效率会明显提升。