刷到代码随想录算法训练营DAY16第六章二叉树part04我明显感觉到这一part和之前几part最不一样的地方递归不再是简单的“套模板”而是开始要求你在返回值、回溯、遍历顺序之间做选择。当天刷完这一趴我最大的感受是——二叉树递归真正的分水岭从这儿开始了。这一part围绕几类高频题展开平衡二叉树、二叉树的所有路径、左叶子之和、找树左下角的值、路径总和。它们看起来是五个题实际是在反复训练三件事第一递归函数到底该返回什么第二什么时候需要手动回溯第三遍历顺序怎么选才不会错。如果你正跟训练营打卡刷到二叉树或者写递归总是磕磕绊绊这篇内容应该能帮上忙。下面直接把当天整理的思路、代码和踩过的坑都写出来给你当参考。1. 今天的刷题范围与整体思路1.1 为什么把这几道题放在一起很多刚开始刷二叉树的朋友会疑惑这一part的考点是不是太散了实际上不是。平衡二叉树考的是后序遍历加返回值设计二叉树的所有路径考的是前序遍历加回溯左叶子之和考的是父节点视角的条件判断找树左下角的值考的是层序和前序的交叉对比路径总和考的是递归终止条件和剪枝边界。把这五道题串起来看相当于把二叉树递归的五个核心命门全点了一遍。如果按这个顺序刷前面一题会给后面一题埋伏笔。比如所有路径里用到的回溯思路到路径总和II会原样再次出现平衡二叉树里通过返回-1做标记的做法在判断对称、判断子树等场景也能复用。所以我个人建议不要跳着刷最好一天内按顺序过一遍第二天再复盘一遍记忆会非常牢固。1.2 递归三要素和遍历顺序先统一在代码随想录前面章节里反复强调递归三要素这里再快速复习一下函数参数和返回值、终止条件、单层递归逻辑。几乎每一道二叉树递归题都可以用三要素拆解。难的并不是三要素本身而是具体场景下该怎么取值。比如返回值到底是布尔、数值还是void这决定了函数的性质。遍历顺序也要同步考虑。前序遍历适合从根出发向下拼接的题目比如所有路径后序遍历适合需要先拿到子树结果再处理的题目比如平衡二叉树、左叶子之和层序遍历则适合按行取数据比如找树左下角的值。搞清楚这些很多“看答案都能看懂自己写却写不出来”的问题就解决了大半。2. 平衡二叉树如何用递归把“判断”变成“求高度”2.1 题意与最容易想到的笨办法题目很直白给定一棵二叉树判断它是否高度平衡也就是每个节点的左右子树高度差不超过1。注意这里是“每个节点”不是只看根节点就行。只要有一个节点不满足整棵树就不平衡。我最开始想到的解法是两层递归先写一个求高度的函数然后从根节点开始判断当前节点左右子树高度差是否满足再递归检查左右子树。逻辑上没问题但效率很差。在极端情况下比如一棵退化成链状的树求根节点高度已经走完整个链再递归求子节点高度又会重复走整体复杂度会退化到O(n^2)。题目数据稍微给大一点就会超时。2.2 一次遍历的解法返回高度用-1标记不平衡后来我用了一个很经典的做法递归函数返回当前节点的高度如果当前子树已经不平衡直接返回-1。这样做的好处是在递归过程中一旦发现不平衡就立刻返回上层函数只需要判断返回值是不是-1不用再重复计算。核心代码我放在下面语言用C方便对照我平时刷题的习惯。int getHeight(TreeNode* root) { if (!root) 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 max(leftHeight, rightHeight) 1; } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; }这里需要解释一下为什么要在拿到leftHeight后马上判断如果左子树已经不平衡那么右子树根本没意义再去递归了提前返回能省掉不必要的调用。这也是“剪枝”的一个雏形后面做路径总和时还会用到。2.3 复杂度分析和常见错误时间复杂度是O(n)每个节点最多访问一次。空间复杂度是递归栈的深度最坏O(n)平均O(logn)。我踩过的坑有两个。第一个是把“高度”和“深度”搞混深度是根到某节点经过的边数高度是某节点到叶子经过的边数递归计算一般用高度逻辑也就是子节点结果加1。第二个是忘记处理-1的提前传递。左右子树顺序写反导致即使子树不平衡父节点还继续算差值最后返回一个奇怪的正数。顺便说一句这道题其实和求最大深度的代码很接近。你可以在纸上对比一下int maxDepth(TreeNode* root) { if (!root) return 0; return max(maxDepth(root-left), maxDepth(root-right)) 1; }getHeight就是maxDepth的变体只是多了平衡性判断。先把maxDepth写熟再改写成平衡判断会顺手很多。3. 二叉树的所有路径递归回溯的第一道坎3.1 题目理解与输出格式这道题要求返回所有从根节点到叶子节点的路径格式是“1-2-5”这样的字符串。树的遍历顺序自然是前序因为我们要从根开始往下拼接字符串。叶子节点是指左右孩子都为空的节点。空树直接返回空列表只有一个根节点时路径就一个节点。你可能会想直接递归遍历不就行了吗难点在于每一条路径是一根独立的线走到左分支之后还得回到当前节点继续走右分支当前已经拼接好的路径不能被右分支覆盖。这就是回溯的来源。3.2 用值传递代替显式回溯在C里最简单的写法是把路径字符串作为值传递每次递归都会产生一个新的副本天然带回了上一个状态。代码如下void traversal(TreeNode* root, string path, vectorstring result) { if (!root) return; path to_string(root-val); if (!root-left !root-right) { result.push_back(path); return; } path -; traversal(root-left, path, result); traversal(root-right, path, result); } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (!root) return result; traversal(root, , result); return result; }注意这里入参是string path不是string path。如果写成引用就必须在递归结束后手动把path恢复到原来的样子否则右子树会带着左子树已经添加的箭头结果全乱。新手最容易犯这个错。3.3 显式回溯的另一种写法如果你希望节省拷贝成本可以用vectorint path递归到叶子时再统一转换成字符串。但入参要写成引用并且在处理完左右子树后pop_back。代码逻辑简单描述一下走到当前节点后path.push_back(root-val)如果到叶子就把path里的值拼起来然后递归左孩子和右孩子递归结束后执行path.pop_back()。这个pop_back就是关键它必须放在递归调用之后。这两种写法没有绝对优劣。面试时用传值法更快写对但如果能讲清楚显式回溯背后的含义往往更加分。我建议把两种都练一遍。3.4 常见错误与调试技巧最容易出错的是递归前不判空直接把空节点当成路径中的节点输出最后出现“1-2-nullptr”这种结果。我的习惯是在调用前判断node-left和node-right是否存在而不是在函数开头判断root是否为空。当然也可以在函数开头判空但拼接逻辑就要更小心。调试的时候可以打印每个递归深度的path或者画一棵小的示例树比如[1,2,3,null,5]手动走一遍回溯过程。我每次遇到递归晕头转向都会用这种极简树把流程走一遍比空想有效得多。4. 左叶子之和站在父节点才能看见的边界条件4.1 左叶子的定义与常见误区题目名称叫左叶子之和很多人第一反应是“叶子节点”但实际要求的是“左叶子”——它是父节点的左孩子同时自己没有任何孩子。也就是说判断一个节点是不是左叶子光看它自己是判断不出来的你必须在它的父节点那一层确认当前节点的左孩子存在并且这个左孩子左右子树都为空。这就是这道题和前面所有题最大的区别视角要从“当前节点”切到“父节点”。4.2 递归实现递归写法很好理解对当前节点先检查左孩子是否为左叶子如果是就累加然后递归去左子树和右子树继续找。因为要先处理完左右子树再累加返回所以整体是后序遍历的思路。int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; int sum 0; if (root-left !root-left-left !root-left-right) { sum root-left-val; } sum sumOfLeftLeaves(root-left); sum sumOfLeftLeaves(root-right); return sum; }大家注意在判断左叶子之后仍然要递归左子树。很多人会因为已经加了左叶子的值就以为不需要再递归左子树了。实际上如果当前节点的左孩子是左叶子那它确实没有孩子递归下去不会再有更深节点但如果当前节点的左孩子不是叶子它下面可能还有左叶子必须继续递归。右子树同理右子树的左子树里也可能存在左叶子。所以无论哪种情况都要把左右子树递归完才不会漏。4.3 迭代解法和思路对比如果不想用递归也可以用栈模拟前序或中序遍历每到一个节点就检查左孩子是否为叶子是就累加。迭代写法适合把递归栈显式化但核心判断条件永远只有那一个root-left !root-left-left !root-left-right。这道题给我的启发是有些二叉树题目不能只盯着节点本身需要往前一层看。类似的还有判断对称二叉树时左右孩子节点的比较也要在某一层配对进行。所以“父节点视角”是一种经常出现的题型套路。5. 找树左下角的值BFS和DFS两条路线5.1 题意与两种常用解法找树左下角的值要求的是二叉树最后一行最左边的节点值。空树情况要看题目约定一般不会给空树。这个题我推荐记两种解法DFS前序遍历和BFS层序遍历。两种思路各有用武之地考场上哪个熟练用哪个。5.2 DFS思路深度优先加先左后右递归遍历时我维护两个变量当前最大深度maxDepth和答案result。遍历顺序用前序并且先递归左子树再递归右子树。因为前序先走左分支当第一次进入一个更大深度时遇到的节点一定是这个深度最左边的节点也就是需要的结果。void dfs(TreeNode* root, int depth, int maxDepth, int result) { if (!root) return; if (depth maxDepth) { maxDepth depth; result root-val; } dfs(root-left, depth 1, maxDepth, result); dfs(root-right, depth 1, maxDepth, result); } int findBottomLeftValue(TreeNode* root) { if (!root) return -1; int maxDepth -1; int result 0; dfs(root, 0, maxDepth, result); return result; }这里的关键是depth作为值传递所以不需要回溯。如果在写递归时把depth改成引用或全局变量那么遍历完左子树后depth必须减回去否则右子树深度计算就会出错。这也是和所有路径题不同的地方那道题路径需要保持状态到多个递归分支所以必须回溯这道题深度直接作为参数传值就行不建议引入显式回溯。5.3 BFS思路从右往左层序遍历BFS解法更直观层序遍历按层从左到右访问节点最后一行第一个节点就是左下角。不过我更喜欢一个更聪明的变体——从右往左做层序遍历这样最后一个出队的节点自然就是最左边那个。from collections import deque def findBottomLeftValue(root): q deque([root]) result root.val while q: node q.popleft() result node.val if node.right: q.append(node.right) if node.left: q.append(node.left) return result代码里先压右孩子再压左孩子出队顺序变成从右到左。最后出队的节点就是整棵树最后一行的最左节点result会保留它的值。这个写法代码量极小面试现场不容易出错。5.4 两种解法怎么选DFS的空间复杂度更小平均O(logn)BFS最坏会用到O(n)的队列。但如果让我现场选我大概率会写BFS因为层序思路直观不需要考虑更新最大深度和结果的条件。如果你的目标是把递归能力练扎实DFS值得多写几遍。把两种解法都掌握后面处理二叉树的公共祖先、最大宽度等问题时理解会深很多。6. 路径总和递归终止条件的精准设计6.1 题意分析与整体思路路径总和的标准问法给定一棵二叉树和一个目标任务值判断是否存在一条从根节点到叶子节点的路径使得路径上所有节点值之和等于目标任务值。这道题如果直接用“求和”的思路需要一路维护当前总和到叶子判断是否等于目标值。但更简洁的写法是反过来递减每经过一个节点就把目标值减去当前节点值递归到叶子时只需要判断剩余目标值是否为0。这样不用额外传一个sum参数。6.2 递归实现叶子作为终止条件bool hasPathSum(TreeNode* root, int targetSum) { if (!root) return false; if (!root-left !root-right) { return targetSum root-val; } return hasPathSum(root-left, targetSum - root-val) || hasPathSum(root-right, targetSum - root-val); }这里的终止条件非常讲究如果root为空就直接返回false不能在空节点上判断targetSum 0否则会得到错误答案。为什么因为从根到叶子的路径必须到真实的叶子节点结束如果递归到空节点就判断和等于把不存在的空子树也算成了一条路径。最典型的反例就是树只有一个根节点且值不等于目标值如果允许空节点判断调用一次空节点后很可能会误判为true。6.3 如果改成输出所有满足条件的路径这道题的进阶版是路径总和II不仅判断存在性还要输出所有满足条件的路径。这时候递归函数返回值就要从bool改成void因为需要遍历完整棵树而且要用path记录当前路径。参考所有路径那道题在递归时需要把当前节点值压入路径到叶子且剩余值为0时复制path到结果集最后弹出来。注意这里不能再用传值法偷懒否则每次递归拷贝整个path空间损耗会很大。剪枝方面要特别小心如果题目没有说明节点值都是正整数就不能拿targetSum剩余值小于0作为剪枝条件。我见过有人想当然加了剪枝结果在负数用例上直接出错。只有题目明确说节点值都是正整数时才可以用剩余值小于0提前返回。这个细节一定要读题。6.4 为什么递归终止条件是最难的部分很多递归问题想不清楚卡就卡在终止条件。路径总和的终止条件是“叶子节点”不是“空节点”平衡二叉树的终止条件是“空节点返回0”最大深度的终止条件也是“空节点返回0”但含义不同。之所以容易混是因为空节点和叶子节点在某些题里都是“结束”但代表的状态完全不一样。我的建议是写递归前先在注释里写清楚“当前节点代表什么状态、满足什么条件时结束”再开始写代码。这个方法从DAY16开始就一直帮我减少低级错误。7. 常见问题与避坑指南7.1 递归函数什么时候需要返回值这一part最大的收获就是学会分辨递归函数返回值的三种典型场景。我整理成一个表场景返回值类型典型题目搜索是否存在一条路径或需要子树验证结果bool路径总和遍历树并收集多个结果void所有路径、路径总和II需要把子树结果向上传递继续处理int / 节点指针最大深度、左叶子之和、最近公共祖先注意平衡二叉树虽然逻辑上是“是否存在不平衡”但实现时返回高度值用-1标记异常这是一种很实用的扩展。不要把这类题框死在bool上。7.2 回溯到底在回什么回溯的本质是撤销上一次操作让变量回到递归前的状态。在二叉树里最典型的是路径数组走完左子树必须把左子节点从路径中移除才能继续走右子树的路径。如果你用值传递那回溯由拷贝完成代码里看不到如果你用引用或全局变量就一定要手动撤销。我见过很多人为了省几个字符用全局path结果一旦忘记pop_backbug非常难找因为答案会带有之前路径的残留节点。建议初学者在练习阶段优先用传值法理解逻辑等熟练后再主动改成显式回溯体会两者的差别。7.3 边界条件速查表二叉树题有一批高频边界条件我直接做成速查表刷题前扫一眼很管用场景返回/处理空树大多数返回0/false/空列表叶子节点左右孩子都为空的节点只有左孩子或右孩子最小深度、左叶子等题要特别小心需要从父节点判断子树左叶子之和、删除节点等递归到空节点一般作为终止或兜底但别当成叶子判断以最小深度为例如果某节点只有左子树没有右子树那么它的最小深度不是2而是左子树最小深度加1。如果直接套用最大深度的对称写法会错误地返回1。这类细节只能在画图和小用例中暴露出来。7.4 这一part刷完后的个人体会DAY16之后我最大的变化是不再追求一遍写对而是开始分析为什么某一步非要这样写。比如平衡二叉树用-1标记路径总和用叶子做终止条件左叶子必须让父节点来判断——这些都不是技巧而是二叉树递归的底层逻辑。白天刷完这五题我晚上又自己做了一遍把所有代码里的递归函数参数和返回值列成一行挨个问自己“如果没有返回值会怎样、如果终止条件换一下会怎样”收获比多刷五道新题还大。后面二叉树part05、part06越来越依赖这个基本功建议你也这样复盘一次。