代码随想录算法训练营走到第13天二叉树进入part03。如果说part01是把递归遍历的底子打牢part02是在层序、翻转、对称这些操作上磨手感那这一天的内容就非常“提神醒脑”二叉树的最大深度、最小深度、完全二叉树的节点个数、平衡二叉树、二叉树的所有路径。这几道题没有一题需要复杂到让你拍脑袋的高级数据结构但每一题都能把“递归三要素”“回溯”和“返回值设计”这层窗户纸捅破。适合刚刷完二叉树前两部分的同学也适合那些线性表刷得很顺、但一碰到递归就发懵的人。先说这个训练营是什么。它是一个按天推进的算法打卡计划把刷题拆成每天可消化的日课每到一个阶段就集中攻克一类题型。第13天正好卡在二叉树从“会遍历”到“会用遍历”的转折点上。很多人在这个阶段最痛苦的不是代码不会写而是拿到一道新题反应不过来这题和第1天学的前序遍历到底有什么关系part03存在的意义就是帮你完成这个迁移。1. 整体设计与思路拆解1.1 三天三段式为什么二叉树要这么排我自己为了写训练营复盘把这13天的题目从头到尾连起来看了一遍发现节奏安排得很讲究part01是先讲节点定义和递归框架part02是层序遍历的一整个家族part03则集中处理二叉树的“属性类问题”。一天之内出现的题目看起来各有各的长相抽象一下其实全在问一件事这棵树长得匀不匀称、叶子在哪、树有多高、节点有多少。这时候再用遍历去套思路就顺了。前序遍历天然适合往深处走后序遍历天然适合先算完子树再汇总到根。part03里最大深度、节点个数、平衡判断全是后序遍历的主场二叉树的所有路径则是前序遍历加回溯的典型应用。你会明显感觉到前两部分的遍历代码不再是一个个孤立的“模板”而是一种可以拼接的“积木”。所以第13天真正训练的能力是把一道题拆成几个子问题每个子问题对应一棵子树的答案最后再决定“根节点要如何处理这些子答案”。这个能力在之后遇到路径总和、二叉搜索树、最近公共祖先、构造二叉树时都会反复用到。1.2 五道题背后的共同骨架我建议你在动手写part03之前先自己列一个“递归骨架”清单递归函数要返回什么是高度、个数、布尔值还是一个路径集合终止条件是什么是遇到空节点返回还是遇到叶子节点返回当前层要做什么是把左右子树的结果取max、加和还是拼接字符串这三句话看着简单但每天训练营作业里至少有三分之一的人折在第二个问题上。以《最小深度》为例很多人直接套《最大深度》的写法空节点返回0然后min(left, right) 1结果遇到单支树就翻车。因为题目里说“最小深度是从根节点到最近叶子节点的最短路径上的节点数”空节点不算叶子你递归到一个只有右孩子的节点时左子树返回0会被误当成有效深度。这个坑我在后面的常见问题章节会专门展开这里先记住一个原则“空节点返回0”只在汇总左右子树时成立涉及叶子的定义就必须把空节点和叶子节点分开处理。1.3 递归和迭代第13天到底该主练哪个part03的四道“属性题”用递归写非常直觉用迭代写也不是不行但我强烈建议这一天优先吃透递归。原因很简单迭代的解法需要显式维护栈而且相当一部分题用栈模拟前序/后序时回溯的时机比递归隐晦得多。比如路径问题用栈迭代你得额外记录“当前节点对应的路径状态”一不小心就串到别的分支上去。如果你实在想练迭代我建议只练两道一是最大深度用层序遍历数层数即可二是完全二叉树的节点个数用层序遍历逐个计数思路直接代码也不复杂。剩下三道题把精力放在递归上性价比更高。等递归写顺了再回头用迭代去验证自己的理解你会发现迭代反而成了“另一种视角”而不是“必须掌握的解法”。2. 核心细节解析与实操要点2.1 最大深度递归最容易写对的一道题《二叉树的最大深度》对应LeetCode第104题是二叉树递归里最经典的“后序汇总”模板。先递归获取左子树高度再递归获取右子树高度根节点的高度就是二者取大再加1。代码长这样class Solution { public: int maxDepth(TreeNode* root) { if (root NULL) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return 1 max(leftDepth, rightDepth); } };很多教程管这题叫“后序遍历”有些人不理解明明求的是“深度”看着根节点先处理子节点这不就是“先下后上”吗对这个“先下后上”就叫后序。你只有先把左子树、右子树的高度算明白才能得出根节点的高度。如果你用前序写也可以维护一个全局变量记录当前深度每往下走一层就更新最大值但那样就需要显式回溯比如递归完左子树要depth--。实际面试时我建议用后序版本代码量少、边界明确而且后续很多题可以直接改。你也会发现part03的节点个数问题和平衡二叉树问题用的都是同一个后序骨架只是返回值从“高度”换成了“个数”或者从“整数”换成了“-1/正常高度”的混合语义。2.2 最小深度最容易栽在“单支树”上最小深度我前面已经点到过坑。先看错误写法int minDepth(TreeNode* root) { if (root NULL) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); }你在力扣一提交面对一个普通满二叉树结果是对的一旦树退化成一条只有右孩子的链结果就错了。比如根节点只有右孩子最小深度按照题目定义应该是2上面代码却会算出1因为左子树的0被min当成最小值取到了。0代表“没有节点”不是“深度为0的叶子”把0和叶子混淆就会得到错误答案。正确写法要区分三种情况class Solution { public: int minDepth(TreeNode* root) { if (root NULL) return 0; if (root-left NULL root-right ! NULL) { return 1 minDepth(root-right); } if (root-left ! NULL root-right NULL) { return 1 minDepth(root-left); } return 1 min(minDepth(root-left), minDepth(root-right)); } };也可以合并成更紧凑的版本int minDepth(TreeNode* root) { if (root NULL) return 0; if (!root-left || !root-right) { return 1 max(minDepth(root-left), minDepth(root-right)); } return 1 min(minDepth(root-left), minDepth(root-right)); }很多初学者看到这个写法会觉得奇怪为什么一边为空的时候要取max因为当左孩子为空时唯一能走的路径是右子树右子树深度就是当前这侧的真实候选深度所以你要“避开”那一边返回的0。这个技巧我一开始也觉得绕后来总结成一句话空孩子不是叶子不能贡献深度候选值。把这条原则记住最小深度基本不会再错。2.3 完全二叉树的节点个数普通递归和“抄近道”优化《完全二叉树的节点个数》是LeetCode第222题。最容易想到的是直接数后序或层序遍历都可以class Solution { public: int countNodes(TreeNode* root) { if (root NULL) return 0; return countNodes(root-left) countNodes(root-right) 1; } };时间复杂度O(n)对于一般二叉树这是标准答案。但既然题目点名“完全二叉树”就有一个利用完全二叉树性质的更优解法一棵完全二叉树如果它的左子树深度和右子树深度相等那它就是一棵满二叉树节点的总数可以直接用2^depth - 1算出来不用再逐节点遍历。判断“满”的方法很简单从根节点一路往左走数出左侧深度再一路往右走数出右侧深度。如果相等直接返回如果不相等就拆成左右子树递归计算。每次递归都有一边会成为满二叉树从而快速返回总体复杂度降到O(log n * log n)在节点特别多时收益明显。class Solution { public: int countNodes(TreeNode* root) { if (root NULL) return 0; int left 0, right 0; TreeNode* cur root; while (cur) { left; cur cur-left; } cur root; while (cur) { right; cur cur-right; } if (left right) { return (1 left) - 1; } return countNodes(root-left) countNodes(root-right) 1; } };这里1 left就是2的left次方注意left已经包含根节点本身所以满节点个数是2^left - 1。这个写法我在训练营里也是练了几遍才习惯因为它比普通递归多了一步“判断是否满”代码看上去不够对称但只要把“满二叉树直接算”理解成一种剪枝就不难接受。在日常开发里2^h - 1这个公式我经常用来做容量估算比如一个高度为20的满二叉树能塞下100多万个节点这个直觉在估算递归栈深度和内存开销时很有用。3. 实操过程与核心环节实现3.1 平衡二叉树如何用“-1”做哨兵《平衡二叉树》是LeetCode第110题。定义很清晰一棵树的每个节点左右子树高度差绝对值不超过1。如果按最直白的思路你会写一个getHeight函数再在isBalanced里比较每个节点是否平衡然后递归检查左右子树。这会重复计算大量子树高度最坏情况是O(n^2)。我强烈推荐用自底向上的做法把“是否平衡”和“当前高度”合并成一个返回值。C里一般用-1表示不平衡非负值表示高度class Solution { public: int getHeight(TreeNode* root) { if (root NULL) return 0; int leftHeight getHeight(root-left); if (leftHeight -1) return -1; int rightHeight getHeight(root-right); if (rightHeight -1) return -1; if (abs(leftHeight - rightHeight) 1) return -1; return 1 max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } };这里最值得琢磨的是为什么用-1而不是-999或别的值。因为高度不会是负数-1和正常的0、1、2等天然不冲突判断起来也简洁返回-1说明这个子树已经不平衡了直接往上抛不用再往下算。这有点像错误处理里的“快速失败”机制一旦某棵子树出问题整条递归链都会迅速中断效率很高。实际调试中我发现很多人会忘了if (leftHeight -1) return -1;这两个检查结果就是左子树不平衡了函数还继续算右子树最后可能因为abs判断把-1和右子树高度差值算得很奇怪导致结果不稳定。把“哨兵值一旦出现就立即向上传播”当成原则就不会漏。3.2 二叉树的所有路径回溯第一次正式登场《二叉树的所有路径》是LeetCode第257题。这也是训练营第13天里我认为最有价值的一道题因为它第一次让你正式接触“回溯”的概念。题目要求返回所有从根到叶子的路径格式是1-2-5这种。递归框架其实是前序遍历每到一个节点就把节点值记录到路径里如果是叶子节点就生成完整字符串不是叶子就继续往下走走完左子树之后要撤掉左子树的节点再走右子树。先看代码class Solution { public: void traversal(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); if (node-left NULL node-right NULL) { 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) { vectorint path; vectorstring result; if (root NULL) return result; traversal(root, path, result); return result; } };这段代码的关键在path是引用类型。你push了一个节点值进去当递归到达叶子时生成路径当递归返回上一层后必须把当前节点从path中弹出来这样兄弟节点才能得到一份“干净的路径”。这个“加入分支 → 递归 → 弹出分支”的动作就是回溯。我刚开始学的时候总以为要复制path担心引用会把不同分支的路径混在一起。其实引用配合pop_back才是正解它让一个vector在不同递归深度里反复复用空间开销从O(n^2)降到O(n)。如果你用传值代码会更好懂但每个分支都会拷贝一份路径叶子节点多时浪费很大。面试里我更推荐引用加回溯的写法并且要能讲清楚为什么pop_back放在递归调用之后。还有一个小细节生成字符串时我先用循环拼了path.size() - 1个元素加-最后一个元素单独拼。如果你直接在循环里对所有元素都加箭头末尾就会多一个-还得再裁掉不够干净。这个写法我从训练营抄到工作里的日志摘要功能中都适用拼接分隔符的最后一项要做特判避免脏尾巴。3.3 从递归到回溯一个完整的执行过程推演为了让回溯更直观我拿一棵简单二叉树举例还不算代码就是三个节点的树根是1左孩子是2右孩子是3。调用traversal(1, path, result)path先变成[1]。节点1不是叶子先判断左孩子存在进入traversal(2, path, result)path变成[1,2]。节点2是叶子生成1-2放入result然后return。注意此时只返回到traversal(1)内部path仍然是[1,2]如果不弹出2下一步进入右孩子traversal(3)时path会变成[1,2,3]错误的路径就出现了。所以在traversal(1)里左孩子递归调用完之后会执行path.pop_back()path变成[1]再进右孩子path变成[1,3]生成1-3。这个执行过程我在带新手时经常让他们自己在纸上画一遍画完就永远不会忘记为什么pop_back放在递归之后。也可以自己在调试器里多看几轮观察path在每次return前后的长度变化。很多人在训练营第13天卡住不是不理解递归而是不理解“递归返回之后的收尾动作”。这个收尾动作就是回溯的本体。4. 常见问题与排查技巧实录4.1 最小深度单支树问题是最高频翻车点我前面已经详细讲过这里再总结成表格方便你“抄作业”情况错误答案来源正确做法左空右不空min把0当成候选值返回1右子树深度右空左不空min把0当成候选值返回1左子树深度左右都空min(0,0)0最终返回1叶子节点深度就是1代码自然满足左右都不空min正常通过返回1min(左深右深)我建议在自己的题解模板里为最小深度单独写一个函数注释标注“空节点不是叶子”避免三个月后回看代码时又踩一遍。4.2 平衡树返回-1时别把高度和布尔值搞混有些题解会用pairbool, int返回其实和-1哨兵等价。但如果你用int返回就一定要记牢getHeight函数里返回值-1既表示“高度无效”又表示“子树不平衡”这是同一个信号的两层含义。自己在代码里加注释时最好写清楚“-1代表子树已经不平衡后续高度不再有意义”。我在训练营群里看到过个别同学把getHeight直接写成bool返回结果算到一半需要高度差时发现拿不到高度只能再开一个辅助函数。所以设计返回值时一定要先想清楚这棵树在“正常”情况下要返回什么异常情况下用哪个值表达“终止递归”。4.3 完全二叉树节点数的位运算细节在(1 left) - 1里left是包含根节点在内的层数。比如完全二叉树高度为3left计算为3节点数是(1 3) - 1 7正好是三层满二叉树的节点数。有些同学会把left写成不包含根节点的高度导致公式变成(1 (left 1)) - 1两种口径都能算对但一定要在代码里保持一致。我通常习惯使用“从根节点往下数的层数”也就是循环访问左右子树时计数为1、2、3这种口径这样公式更直观。另外如果left和right不相等说明这棵子树不是满的需要递归进左右孩子继续计算。但有一点要注意完全二叉树的递归方向不是随意的它等于是在利用“至少有一侧是满二叉树”的规律让每一层都能跳过一整片节点。你可以试着画一棵只有5个节点的完全二叉树会发现右侧深度比左侧小1递归右侧时很快算出满树结果左侧则需要再拆一层整个计算过程非常灵巧。4.4 路径拼接的性能小问题如果你在《二叉树的所有路径》里用字符串拼接注意result.push_back(s)之前不要再把path塞进result否则结果里会出现vectorint而不是字符串。这个问题看着低级但我在用C刷题时确实见过有人把path直接push到类型为vectorstring的结果里导致编译报错。更隐蔽的是如果把to_string和-的顺序写反生成的字符串顺序会是错误的。还有一个性能习惯如果是大量路径拼接每次path.push_back(node-val)后直接to_string并追加到字符串里而不是等叶子节点时统一遍历也是常见的提速方式。不过这题节点数一般不大保持思路清晰比极限优化更重要。5. 我的一个私藏技巧用“返回值三问”过流程第13天刷完我沉淀出一个自用的检查方法叫“返回值三问”。每写完一道题先不看测试用例问自己三个问题空节点能返回什么叶子节点能返回什么普通节点拿到左右子树结果后要做什么操作才能拼出自己的结果比如最大深度空节点返回0叶子节点返回1普通节点取max1。节点个数空节点返回0叶子节点返回1普通节点左右加和再加1。平衡树空节点返回0叶子节点返回1普通节点要检查左右的高度差不平衡就返回-1。路径问题空节点直接不进入递归叶子节点生成结果普通节点继续递归左右分支。这样一梳理你会发现五道题的本质真的是同一套思路只是“操作”和“返回值”不同。这个方法我后来带到工作里也极其好用。比如做递归树状菜单遍历、评论列表的嵌套渲染处理逻辑本质上也是先决定“空节点返回什么”再决定“汇总动作是什么”。题刷完不只是为了面试这种抽象思维在真实代码里救过我很多次。6. 最后再分享一点当天刷题的时间安排如果你今天刚开始写part03我建议别一口吃成胖子。先把最大深度和节点个数一起做因为都是后序递归的温柔版一个改max一个改写完会有“原来如此”的爽感。再做最小深度和平衡二叉树这两题要重点体会边界条件的差异适合同一天对比记忆。最后做二叉树的所有路径因为它引入了回溯需要额外消化“递归返回后的收尾动作”单独留出充足时间更稳妥。我在实际练习中通常是在晚上集中刷完前四题第二天早上把路径题的递归回溯过程在纸上推演一遍再手写一遍代码。手写的时候不查资料写不出来就回去看注释直到能一次性默写出正确解法。这个过程不聪明但对巩固递归的肌肉记忆非常有效尤其适合基础不是特别扎实的人。第13天过了后面还有二叉搜索树、公共祖先、构造二叉树等一堆硬骨头等着啃但只要你把这一天的“属性题”和“路径回溯”啃透我觉得后续至少一半的代码你都会觉得眼熟。每次以为自己在学新题其实都是在复习旧模板这种感觉就是你真正入门了。 二叉树深度、节点数与路径回溯：一次吃透递归与回溯核心
代码随想录算法训练营走到第13天二叉树进入part03。如果说part01是把递归遍历的底子打牢part02是在层序、翻转、对称这些操作上磨手感那这一天的内容就非常“提神醒脑”二叉树的最大深度、最小深度、完全二叉树的节点个数、平衡二叉树、二叉树的所有路径。这几道题没有一题需要复杂到让你拍脑袋的高级数据结构但每一题都能把“递归三要素”“回溯”和“返回值设计”这层窗户纸捅破。适合刚刷完二叉树前两部分的同学也适合那些线性表刷得很顺、但一碰到递归就发懵的人。先说这个训练营是什么。它是一个按天推进的算法打卡计划把刷题拆成每天可消化的日课每到一个阶段就集中攻克一类题型。第13天正好卡在二叉树从“会遍历”到“会用遍历”的转折点上。很多人在这个阶段最痛苦的不是代码不会写而是拿到一道新题反应不过来这题和第1天学的前序遍历到底有什么关系part03存在的意义就是帮你完成这个迁移。1. 整体设计与思路拆解1.1 三天三段式为什么二叉树要这么排我自己为了写训练营复盘把这13天的题目从头到尾连起来看了一遍发现节奏安排得很讲究part01是先讲节点定义和递归框架part02是层序遍历的一整个家族part03则集中处理二叉树的“属性类问题”。一天之内出现的题目看起来各有各的长相抽象一下其实全在问一件事这棵树长得匀不匀称、叶子在哪、树有多高、节点有多少。这时候再用遍历去套思路就顺了。前序遍历天然适合往深处走后序遍历天然适合先算完子树再汇总到根。part03里最大深度、节点个数、平衡判断全是后序遍历的主场二叉树的所有路径则是前序遍历加回溯的典型应用。你会明显感觉到前两部分的遍历代码不再是一个个孤立的“模板”而是一种可以拼接的“积木”。所以第13天真正训练的能力是把一道题拆成几个子问题每个子问题对应一棵子树的答案最后再决定“根节点要如何处理这些子答案”。这个能力在之后遇到路径总和、二叉搜索树、最近公共祖先、构造二叉树时都会反复用到。1.2 五道题背后的共同骨架我建议你在动手写part03之前先自己列一个“递归骨架”清单递归函数要返回什么是高度、个数、布尔值还是一个路径集合终止条件是什么是遇到空节点返回还是遇到叶子节点返回当前层要做什么是把左右子树的结果取max、加和还是拼接字符串这三句话看着简单但每天训练营作业里至少有三分之一的人折在第二个问题上。以《最小深度》为例很多人直接套《最大深度》的写法空节点返回0然后min(left, right) 1结果遇到单支树就翻车。因为题目里说“最小深度是从根节点到最近叶子节点的最短路径上的节点数”空节点不算叶子你递归到一个只有右孩子的节点时左子树返回0会被误当成有效深度。这个坑我在后面的常见问题章节会专门展开这里先记住一个原则“空节点返回0”只在汇总左右子树时成立涉及叶子的定义就必须把空节点和叶子节点分开处理。1.3 递归和迭代第13天到底该主练哪个part03的四道“属性题”用递归写非常直觉用迭代写也不是不行但我强烈建议这一天优先吃透递归。原因很简单迭代的解法需要显式维护栈而且相当一部分题用栈模拟前序/后序时回溯的时机比递归隐晦得多。比如路径问题用栈迭代你得额外记录“当前节点对应的路径状态”一不小心就串到别的分支上去。如果你实在想练迭代我建议只练两道一是最大深度用层序遍历数层数即可二是完全二叉树的节点个数用层序遍历逐个计数思路直接代码也不复杂。剩下三道题把精力放在递归上性价比更高。等递归写顺了再回头用迭代去验证自己的理解你会发现迭代反而成了“另一种视角”而不是“必须掌握的解法”。2. 核心细节解析与实操要点2.1 最大深度递归最容易写对的一道题《二叉树的最大深度》对应LeetCode第104题是二叉树递归里最经典的“后序汇总”模板。先递归获取左子树高度再递归获取右子树高度根节点的高度就是二者取大再加1。代码长这样class Solution { public: int maxDepth(TreeNode* root) { if (root NULL) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return 1 max(leftDepth, rightDepth); } };很多教程管这题叫“后序遍历”有些人不理解明明求的是“深度”看着根节点先处理子节点这不就是“先下后上”吗对这个“先下后上”就叫后序。你只有先把左子树、右子树的高度算明白才能得出根节点的高度。如果你用前序写也可以维护一个全局变量记录当前深度每往下走一层就更新最大值但那样就需要显式回溯比如递归完左子树要depth--。实际面试时我建议用后序版本代码量少、边界明确而且后续很多题可以直接改。你也会发现part03的节点个数问题和平衡二叉树问题用的都是同一个后序骨架只是返回值从“高度”换成了“个数”或者从“整数”换成了“-1/正常高度”的混合语义。2.2 最小深度最容易栽在“单支树”上最小深度我前面已经点到过坑。先看错误写法int minDepth(TreeNode* root) { if (root NULL) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); }你在力扣一提交面对一个普通满二叉树结果是对的一旦树退化成一条只有右孩子的链结果就错了。比如根节点只有右孩子最小深度按照题目定义应该是2上面代码却会算出1因为左子树的0被min当成最小值取到了。0代表“没有节点”不是“深度为0的叶子”把0和叶子混淆就会得到错误答案。正确写法要区分三种情况class Solution { public: int minDepth(TreeNode* root) { if (root NULL) return 0; if (root-left NULL root-right ! NULL) { return 1 minDepth(root-right); } if (root-left ! NULL root-right NULL) { return 1 minDepth(root-left); } return 1 min(minDepth(root-left), minDepth(root-right)); } };也可以合并成更紧凑的版本int minDepth(TreeNode* root) { if (root NULL) return 0; if (!root-left || !root-right) { return 1 max(minDepth(root-left), minDepth(root-right)); } return 1 min(minDepth(root-left), minDepth(root-right)); }很多初学者看到这个写法会觉得奇怪为什么一边为空的时候要取max因为当左孩子为空时唯一能走的路径是右子树右子树深度就是当前这侧的真实候选深度所以你要“避开”那一边返回的0。这个技巧我一开始也觉得绕后来总结成一句话空孩子不是叶子不能贡献深度候选值。把这条原则记住最小深度基本不会再错。2.3 完全二叉树的节点个数普通递归和“抄近道”优化《完全二叉树的节点个数》是LeetCode第222题。最容易想到的是直接数后序或层序遍历都可以class Solution { public: int countNodes(TreeNode* root) { if (root NULL) return 0; return countNodes(root-left) countNodes(root-right) 1; } };时间复杂度O(n)对于一般二叉树这是标准答案。但既然题目点名“完全二叉树”就有一个利用完全二叉树性质的更优解法一棵完全二叉树如果它的左子树深度和右子树深度相等那它就是一棵满二叉树节点的总数可以直接用2^depth - 1算出来不用再逐节点遍历。判断“满”的方法很简单从根节点一路往左走数出左侧深度再一路往右走数出右侧深度。如果相等直接返回如果不相等就拆成左右子树递归计算。每次递归都有一边会成为满二叉树从而快速返回总体复杂度降到O(log n * log n)在节点特别多时收益明显。class Solution { public: int countNodes(TreeNode* root) { if (root NULL) return 0; int left 0, right 0; TreeNode* cur root; while (cur) { left; cur cur-left; } cur root; while (cur) { right; cur cur-right; } if (left right) { return (1 left) - 1; } return countNodes(root-left) countNodes(root-right) 1; } };这里1 left就是2的left次方注意left已经包含根节点本身所以满节点个数是2^left - 1。这个写法我在训练营里也是练了几遍才习惯因为它比普通递归多了一步“判断是否满”代码看上去不够对称但只要把“满二叉树直接算”理解成一种剪枝就不难接受。在日常开发里2^h - 1这个公式我经常用来做容量估算比如一个高度为20的满二叉树能塞下100多万个节点这个直觉在估算递归栈深度和内存开销时很有用。3. 实操过程与核心环节实现3.1 平衡二叉树如何用“-1”做哨兵《平衡二叉树》是LeetCode第110题。定义很清晰一棵树的每个节点左右子树高度差绝对值不超过1。如果按最直白的思路你会写一个getHeight函数再在isBalanced里比较每个节点是否平衡然后递归检查左右子树。这会重复计算大量子树高度最坏情况是O(n^2)。我强烈推荐用自底向上的做法把“是否平衡”和“当前高度”合并成一个返回值。C里一般用-1表示不平衡非负值表示高度class Solution { public: int getHeight(TreeNode* root) { if (root NULL) return 0; int leftHeight getHeight(root-left); if (leftHeight -1) return -1; int rightHeight getHeight(root-right); if (rightHeight -1) return -1; if (abs(leftHeight - rightHeight) 1) return -1; return 1 max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } };这里最值得琢磨的是为什么用-1而不是-999或别的值。因为高度不会是负数-1和正常的0、1、2等天然不冲突判断起来也简洁返回-1说明这个子树已经不平衡了直接往上抛不用再往下算。这有点像错误处理里的“快速失败”机制一旦某棵子树出问题整条递归链都会迅速中断效率很高。实际调试中我发现很多人会忘了if (leftHeight -1) return -1;这两个检查结果就是左子树不平衡了函数还继续算右子树最后可能因为abs判断把-1和右子树高度差值算得很奇怪导致结果不稳定。把“哨兵值一旦出现就立即向上传播”当成原则就不会漏。3.2 二叉树的所有路径回溯第一次正式登场《二叉树的所有路径》是LeetCode第257题。这也是训练营第13天里我认为最有价值的一道题因为它第一次让你正式接触“回溯”的概念。题目要求返回所有从根到叶子的路径格式是1-2-5这种。递归框架其实是前序遍历每到一个节点就把节点值记录到路径里如果是叶子节点就生成完整字符串不是叶子就继续往下走走完左子树之后要撤掉左子树的节点再走右子树。先看代码class Solution { public: void traversal(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); if (node-left NULL node-right NULL) { 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) { vectorint path; vectorstring result; if (root NULL) return result; traversal(root, path, result); return result; } };这段代码的关键在path是引用类型。你push了一个节点值进去当递归到达叶子时生成路径当递归返回上一层后必须把当前节点从path中弹出来这样兄弟节点才能得到一份“干净的路径”。这个“加入分支 → 递归 → 弹出分支”的动作就是回溯。我刚开始学的时候总以为要复制path担心引用会把不同分支的路径混在一起。其实引用配合pop_back才是正解它让一个vector在不同递归深度里反复复用空间开销从O(n^2)降到O(n)。如果你用传值代码会更好懂但每个分支都会拷贝一份路径叶子节点多时浪费很大。面试里我更推荐引用加回溯的写法并且要能讲清楚为什么pop_back放在递归调用之后。还有一个小细节生成字符串时我先用循环拼了path.size() - 1个元素加-最后一个元素单独拼。如果你直接在循环里对所有元素都加箭头末尾就会多一个-还得再裁掉不够干净。这个写法我从训练营抄到工作里的日志摘要功能中都适用拼接分隔符的最后一项要做特判避免脏尾巴。3.3 从递归到回溯一个完整的执行过程推演为了让回溯更直观我拿一棵简单二叉树举例还不算代码就是三个节点的树根是1左孩子是2右孩子是3。调用traversal(1, path, result)path先变成[1]。节点1不是叶子先判断左孩子存在进入traversal(2, path, result)path变成[1,2]。节点2是叶子生成1-2放入result然后return。注意此时只返回到traversal(1)内部path仍然是[1,2]如果不弹出2下一步进入右孩子traversal(3)时path会变成[1,2,3]错误的路径就出现了。所以在traversal(1)里左孩子递归调用完之后会执行path.pop_back()path变成[1]再进右孩子path变成[1,3]生成1-3。这个执行过程我在带新手时经常让他们自己在纸上画一遍画完就永远不会忘记为什么pop_back放在递归之后。也可以自己在调试器里多看几轮观察path在每次return前后的长度变化。很多人在训练营第13天卡住不是不理解递归而是不理解“递归返回之后的收尾动作”。这个收尾动作就是回溯的本体。4. 常见问题与排查技巧实录4.1 最小深度单支树问题是最高频翻车点我前面已经详细讲过这里再总结成表格方便你“抄作业”情况错误答案来源正确做法左空右不空min把0当成候选值返回1右子树深度右空左不空min把0当成候选值返回1左子树深度左右都空min(0,0)0最终返回1叶子节点深度就是1代码自然满足左右都不空min正常通过返回1min(左深右深)我建议在自己的题解模板里为最小深度单独写一个函数注释标注“空节点不是叶子”避免三个月后回看代码时又踩一遍。4.2 平衡树返回-1时别把高度和布尔值搞混有些题解会用pairbool, int返回其实和-1哨兵等价。但如果你用int返回就一定要记牢getHeight函数里返回值-1既表示“高度无效”又表示“子树不平衡”这是同一个信号的两层含义。自己在代码里加注释时最好写清楚“-1代表子树已经不平衡后续高度不再有意义”。我在训练营群里看到过个别同学把getHeight直接写成bool返回结果算到一半需要高度差时发现拿不到高度只能再开一个辅助函数。所以设计返回值时一定要先想清楚这棵树在“正常”情况下要返回什么异常情况下用哪个值表达“终止递归”。4.3 完全二叉树节点数的位运算细节在(1 left) - 1里left是包含根节点在内的层数。比如完全二叉树高度为3left计算为3节点数是(1 3) - 1 7正好是三层满二叉树的节点数。有些同学会把left写成不包含根节点的高度导致公式变成(1 (left 1)) - 1两种口径都能算对但一定要在代码里保持一致。我通常习惯使用“从根节点往下数的层数”也就是循环访问左右子树时计数为1、2、3这种口径这样公式更直观。另外如果left和right不相等说明这棵子树不是满的需要递归进左右孩子继续计算。但有一点要注意完全二叉树的递归方向不是随意的它等于是在利用“至少有一侧是满二叉树”的规律让每一层都能跳过一整片节点。你可以试着画一棵只有5个节点的完全二叉树会发现右侧深度比左侧小1递归右侧时很快算出满树结果左侧则需要再拆一层整个计算过程非常灵巧。4.4 路径拼接的性能小问题如果你在《二叉树的所有路径》里用字符串拼接注意result.push_back(s)之前不要再把path塞进result否则结果里会出现vectorint而不是字符串。这个问题看着低级但我在用C刷题时确实见过有人把path直接push到类型为vectorstring的结果里导致编译报错。更隐蔽的是如果把to_string和-的顺序写反生成的字符串顺序会是错误的。还有一个性能习惯如果是大量路径拼接每次path.push_back(node-val)后直接to_string并追加到字符串里而不是等叶子节点时统一遍历也是常见的提速方式。不过这题节点数一般不大保持思路清晰比极限优化更重要。5. 我的一个私藏技巧用“返回值三问”过流程第13天刷完我沉淀出一个自用的检查方法叫“返回值三问”。每写完一道题先不看测试用例问自己三个问题空节点能返回什么叶子节点能返回什么普通节点拿到左右子树结果后要做什么操作才能拼出自己的结果比如最大深度空节点返回0叶子节点返回1普通节点取max1。节点个数空节点返回0叶子节点返回1普通节点左右加和再加1。平衡树空节点返回0叶子节点返回1普通节点要检查左右的高度差不平衡就返回-1。路径问题空节点直接不进入递归叶子节点生成结果普通节点继续递归左右分支。这样一梳理你会发现五道题的本质真的是同一套思路只是“操作”和“返回值”不同。这个方法我后来带到工作里也极其好用。比如做递归树状菜单遍历、评论列表的嵌套渲染处理逻辑本质上也是先决定“空节点返回什么”再决定“汇总动作是什么”。题刷完不只是为了面试这种抽象思维在真实代码里救过我很多次。6. 最后再分享一点当天刷题的时间安排如果你今天刚开始写part03我建议别一口吃成胖子。先把最大深度和节点个数一起做因为都是后序递归的温柔版一个改max一个改写完会有“原来如此”的爽感。再做最小深度和平衡二叉树这两题要重点体会边界条件的差异适合同一天对比记忆。最后做二叉树的所有路径因为它引入了回溯需要额外消化“递归返回后的收尾动作”单独留出充足时间更稳妥。我在实际练习中通常是在晚上集中刷完前四题第二天早上把路径题的递归回溯过程在纸上推演一遍再手写一遍代码。手写的时候不查资料写不出来就回去看注释直到能一次性默写出正确解法。这个过程不聪明但对巩固递归的肌肉记忆非常有效尤其适合基础不是特别扎实的人。第13天过了后面还有二叉搜索树、公共祖先、构造二叉树等一堆硬骨头等着啃但只要你把这一天的“属性题”和“路径回溯”啃透我觉得后续至少一半的代码你都会觉得眼熟。每次以为自己在学新题其实都是在复习旧模板这种感觉就是你真正入门了。