代码随想录刷到Day13这天安排的四道二叉树题目很有意思222完全二叉树的节点个数、110平衡二叉树、257二叉树的所有路径、404左叶子之和。单看每一道好像都在考不同的知识点但放一起刷的时候会发现它们其实是在用四个角度训练同一件事——对递归遍历的理解深度。很多朋友刷二叉树容易陷入一个误区题刷了不少但每一道都是背模板换一道变形题就发懵。这四道题恰好能把这个问题暴露得很彻底它们都用基础的递归遍历就能解但如果没有真正想清楚递归返回什么什么时候处理结点回溯发生在哪一层就很容易写出能跑但性能很差或者边界一碰就崩的代码。这篇就把这四道题放在一起做个完整拆解从最容易想到的解法讲到优化方案再补上刷题时最常见的运行时错误排查思路。适合正在按代码随想录路线刷题、或者二叉树递归还没形成体系化理解的人看完应该能把递归返回值和参数设计这件事想得更透。1. 先把这四道题放在一起看它们到底在考什么单独刷题的时候容易只见树木不见森林总觉得222题考完全二叉树性质、110题考平衡定义、257题考回溯、404题考叶子判断彼此之间没什么关系。但换个角度看这四道题的解法全部建立在同一个基础上对二叉树的深度优先遍历尤其是后序遍历的返回值设计。222题根本不需要完全二叉树性质也能做普通递归遍历统计节点数就完事优化解法才用上完全二叉树的满树特性。110题的核心也不是怎么求高度而是怎么在求高度的过程中顺便判断平衡。257题的本质是前序遍历加回溯。404题则需要想清楚左叶子这个定义应该站在哪个结点视角去判断。换句话说这四道题覆盖了递归三要素里的每一个细节参数怎么设计、返回值怎么设计、终止条件怎么设计、单层递归逻辑怎么组织再加一个回溯的概念在里面。这个体系梳理清楚之后再回头看代码随想录里二叉树章节的安排逻辑就很明显了——前面的题练的是遍历这几道题练的是在遍历过程中收集信息。区别在于单纯的遍历只关心走到哪了而这四道题要求你走到某个位置时知道该怎么作决策。这是二叉树题目从入门到进阶之间很重要的一道坎。也有个实际的备考体验这四道题在面试里出现的频率都不低。222题常作为有没有比O(n)更快的方法的追问题110题几乎是平衡树相关话题的必背题257题是递归回溯的经典入门404题虽然简单但左叶子那个边界判断经常有人错。把它们一次吃透后面遇到类似题会轻松非常多。2. 222 完全二叉树的节点个数从暴力统计到利用满树性质2.1 最直接的思路当普通二叉树处理先说最简单、也最容易想到的方法。如果对完全二叉树这个条件不加任何利用这就是一道彻头彻尾的遍历计数题任何遍历方式都能解决。递归写法非常直白int countNodes(TreeNode* root) { if (root nullptr) return 0; return countNodes(root-left) countNodes(root-right) 1; }这个代码就是标准的后序遍历空结点返回0非空结点返回左子树节点数加右子树节点数再加自己。时间复杂度O(n)空间复杂度是递归栈深度O(log n)完全二叉树高度维持在log级别。迭代写法可以用层序遍历队列里每个结点弹出时计数加一就行。思路和递归一致只是换成显式的遍历流程。第一次刷这道题的人写出这个解法就足够了。但它显然不是这道题想让你停留在的地方因为题目特意强调了完全二叉树。面试官如果问能不能再快一点你需要给得出下面的优化方案。2.2 利用完全二叉树性质把时间压到O(log n * log n)完全二叉树和普通二叉树最大的区别在于一个结点如果左子树和右子树高度相等那么这棵子树必然是满二叉树。满二叉树的节点数可以直接用公式2^h - 1计算其中h为树的高度从1开始计完全不需要往下递归。这个性质怎么用对当前结点分别沿着左边界和右边界一直走到头数出左深度和右深度。如果两者相等说明当前子树满直接返回 (1 depth) - 1。如果不等说明当前子树不满那就递归计算左子树和右子树的节点数再加1。int countNodes(TreeNode* root) { if (root nullptr) return 0; TreeNode* left root-left; TreeNode* right root-right; int leftDepth 0, rightDepth 0; while (left) { left left-left; leftDepth; } while (right) { right right-right; rightDepth; } if (leftDepth rightDepth) { return (2 leftDepth) - 1; } return countNodes(root-left) countNodes(root-right) 1; }注意这里的细节左深度是从root的左孩子开始往下数的所以当root不是空结点时leftDepth初始为0。如果root的左孩子为空说明左深度和右深度都是0当前子树其实就是只有root一个结点的满二叉树(2 0) - 1 1逻辑是对的。递归过程中每一层只有一侧会继续往下走因为完全二叉树的任何一个结点它的左右子树中至少有一个是满二叉树。这个结论可以画个图验证一下最后一层结点从左到右连续排列那么每个结点右侧的子树要么满要么只缺右侧部分但不会两边都缺。所以递归深度其实是树的高度每次判断又需要O(log n)去走边界整体复杂度就是O(log n * log n)。2.3 避坑要点位运算别写错我在第一次写这个优化版本时犯过一个低级错误把 (2 leftDepth) - 1 写成了 (1 leftDepth) - 1。这两个式子看起来差不多但语义完全不同。假设满二叉树高度为h根结点高度为1节点数是2^h - 1。当leftDepth表示从根往下走到底步数时这个步数等于h - 1。所以2^(leftDepth1) - 1等同于2^h - 1也就是代码里的 (2 leftDepth) - 1。如果错写成 (1 leftDepth) - 1就相当于算成了2^(h-1) - 1结果直接少了一半。数字举个例子一棵只有根结点的树leftDepth0正确应该返回1。错误写法 (1 0) - 1 0直接错了。所以当树的深度很浅时这个问题特别容易暴露出来。另外有一个小坑有些资料里写的是1 depth但它们的depth是从1开始定义的逻辑也行关键是和你的循环初始值保持一致。建议手写推导一遍而不是背公式。3. 110 平衡二叉树为什么自顶向下是O(n²)而自底向上是O(n)3.1 平衡二叉树的定义和直觉误区题目里的平衡二叉树定义是每个结点的左右子树高度差的绝对值不超过1并且左右子树本身也必须是平衡二叉树。注意这里强调的是每个结点不是只看根结点。很多新手第一次写这道题的思路是这样的写一个求高度的函数然后递归判断每个结点是否平衡判断时调用高度函数。int getHeight(TreeNode* root) { if (root nullptr) return 0; return max(getHeight(root-left), getHeight(root-right)) 1; } bool isBalanced(TreeNode* root) { if (root nullptr) return true; int left getHeight(root-left); int right getHeight(root-right); return abs(left - right) 1 isBalanced(root-left) isBalanced(root-right); }这个写法逻辑上完全正确但它有一个严重的问题getHeight会被反复调用。isBalanced到每个结点时都会把它下面所有子树重新遍历一遍求高度而求高度本身又是O(n)的。一个像链一样歪斜的树根结点求高度要遍历n个结点下一层遍历n-1个整体就是O(n²)。用这个写法去LeetCode跑大样例可能会超时也可能勉强通过取决于测试数据的强度。但它绝不是这道题该有的最优解。3.2 自底向上让高度函数顺便做判断正确思路是把求高度和判断平衡合并到一次后序遍历里。递归函数返回一个特殊值来同时表达两层含义正常返回树的高度一旦发现不平衡就返回-1作为标记。这样对于任何一个结点先递归拿到左子树高度再拿到右子树高度如果两边都是合法的非负值且高度差不超过1就返回正常高度。否则返回-1。最终根结点返回值如果不是-1整棵树就是平衡的。int getHeight(TreeNode* root) { if (root nullptr) 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; }这段代码的精髓是剪枝一旦某个子树返回-1上层会立刻判断出来并把-1一路传上去不再继续做无意义的计算。因此时间复杂度严格O(n)每个结点只访问一次空间复杂度O(n)对应递归栈深度最坏情况树退化成链表。3.3 这个思想在AVL树和很多递归题里的通用性-1作为非法标记这种手法在二叉树里出现的频率远比想象中高。比如求二叉树的最大直径需要在求高度的过程中顺便维护直径再比如判断二叉树是否对称需要同时递归比较左右子树而不是单独遍历。这类在递归过程中携带一个不可达的哨兵值的思路本质上是在没有额外全局变量的前提下让递归返回值携带更多信息。另外还有一个小优化点如果不希望用-1标记也可以把函数签名改成返回一个结构体同时包含height和isBalanced两个字段。代码会相对啰嗦一些但在工程上可读性更好。刷题时用-1是性价比最高的写法面试时如果面试官追问可以把结构体方案作为补充提一嘴。这道题我踩过的坑是只判断了根结点左右子树高度差忘了递归判断子树本身。换句话说写成了只算一次高度就结束。这样遇到一个根结点平衡但左子树内部不平衡的样例就直接错了。所以写完代码之后至少要自己构造一个三层以上的不平衡树去手动走一遍比如左子树里有一个深层结点导致左子树内部高度差为2但根结点左右子树整体高度差恰好为1。4. 257 二叉树的所有路径回溯的真面目在这道题里看最清楚4.1 递归思路前序遍历加路径记录题目要求返回所有从根到叶子的路径给定的是字符串形式比如 1-2-5。这个需求天然对应前序遍历先访问根再递归左子树再递归右子树。在递归过程中需要维护一个当前路径走到叶子时把路径转成字符串存进结果数组。很多第一次接触回溯的人看这道题的代码会觉得奇怪为什么递归完左子树之后要把路径最后一项弹出去这其实就是回溯的标准操作。因为路径是递归过程中一路携带的状态如果不把当前结点从路径里移除递归回到这个结点再去右子树时路径里会残留左子树走过的结点导致右子树路径里出现无关结点。vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root nullptr) return result; traversal(root, path, result); return result; } void traversal(TreeNode* cur, vectorint path, vectorstring result) { path.push_back(cur-val); if (cur-left nullptr cur-right nullptr) { string strPath; for (int i 0; i path.size() - 1; i) { strPath to_string(path[i]); strPath -; } strPath to_string(path[path.size() - 1]); result.push_back(strPath); return; } if (cur-left) { traversal(cur-left, path, result); path.pop_back(); // 回溯 } if (cur-right) { traversal(cur-right, path, result); path.pop_back(); // 回溯 } }4.2 为什么说递归和回溯是一体两面这道题里的path是作为一个引用传入递归函数的整个递归过程中只有一个path数组被反复修改。正因为它是共享的状态所以必须在递归完成后还原现场。这就是回溯的核心在递归返回父结点之前把当前函数对共享状态的修改撤销掉保证父结点继续处理下一个分支时看到的状态和递归之前完全一致。可以对比另一种写法把path直接按值传入递归函数。这样每个分支都会拷贝一份完整的路径不需要回溯。代码写起来更简单但空间开销会显著变大。在路径长度很短时差别不明显但原理上每次递归拷贝都是一个O(深度)的额外开销。刷题时我更推荐引用加回溯的写法因为很多更复杂的回溯题不可能靠拷贝解决提前养成这个习惯后面省事很多。4.3 输出格式的细节别大意题目要求路径格式是1-2-5最后一个结点后面不能有箭头。初学者容易在循环里统一加箭头最后多出一个-需要去处理。我习惯的做法是上面代码里的写法遍历到倒数第二个结点为止单独处理最后一个结点。还有一种常见写法是先拼-val再存结果if (cur-left nullptr cur-right nullptr) { result.push_back(strPath to_string(cur-val)); }配合在递归时传strPath to_string(cur-val) -这种方案代码会短一些但需要想清楚字符串拼接的位置。两种都能过选一种自己顺手的关键是手动推演一次1-2-3这种三条路径的样例确保箭头位置没问题。5. 404 左叶子之和最容易栽在什么算左叶子5.1 左叶子的完整定义比想象中严格题目要求计算所有左叶子节点的值之和。什么叫左叶子必须同时满足两个条件第一它是一个叶子节点即没有左右孩子第二它是其父节点的左孩子。这个定义初看很简单但实际写代码时有一个很常见的思维陷阱试图在递归到当前节点时判断当前节点是不是左叶子。但问题是递归函数走到一个节点时你只知道这个节点本身的情况无法知道它是父节点的左孩子还是右孩子。除非在参数里额外传一个标志位否则判断不了。一个更干净的思路是在父节点处做判断。也就是遍历到某个非空节点A时检查它的左孩子是否存在以及这个左孩子是不是叶子。如果是就把左孩子的值加进结果。这相当于把左叶子的判定工作放到它的父亲节点那里完成。5.2 递归写法把父节点视角贯彻到底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; }这个写法里递归函数的作用是遍历所有节点并在每个节点处检查它的左孩子是否是左叶子。所以即使root-left本身是一个左叶子我们依然要继续递归进它的右子树右子树是空的函数直接返回0。实际运行时会发现对任何一个左叶子的子树调用递归由于它是叶子recursion会在开头直接返回0不会产生额外干扰。另一种更贴合定义但代码稍长的写法是给递归函数传一个布尔参数表示当前节点是否为父节点的左孩子int dfs(TreeNode* root, bool isLeft) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr) { return isLeft ? root-val : 0; } return dfs(root-left, true) dfs(root-right, false); } int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; return dfs(root-left, true) dfs(root-right, false); }这个写法把左叶子的判断拆得很直白只有叶子且isLeft为true时才把值加到和里。两种写法思路不同但结果一致。我个人更推荐第一种写法因为它不需要额外引入标志位但第二种写法在面试中做讲解时其实更容易说清楚左叶子的定义。5.3 边界情况自查表这道题虽然简单但很容易在边界上翻车。最经典的问题是只有一个根节点没有左孩子那左叶子之和应该是0。很多人在递归里可能会把根节点本身算进去导致输出错误。好在这种题目LeetCode的样例一般会覆盖到自己手写时也要主动检查这几类空树返回0。只有一个根节点返回0。整棵树只有左叶子比如 root(1)-left(2)返回2。多层嵌套的树比如 root(1) - left(2) - left(4)4是左叶子2本身不是叶子所以返回4。一棵树的右子树上也有叶子但右叶子不计入。把这几类case在心里跑一遍这道题基本就稳了。另外也可以写一个迭代解法练手层序遍历或者栈模拟深度遍历在每个出队/出栈节点处同样用父节点视角判断左孩子。迭代解法多写几遍对理解栈和队列在二叉树遍历中的角色也有帮助。6. 四道题串起来看二叉树递归的设计范式6.1 三要素在这四道题里的具体落点代码随想录反复强调递归三要素参数和返回值、终止条件、单层递归逻辑。这四道题正好把三要素的每个方面都考到了。222题和110题的核心在返回值设计222返回的是节点个数110返回的是高度或-1标记。返回值一旦设计错了后面全乱。257题的核心在参数设计path要作为引用传入并配合回溯result作为结果收集器。404题的核心在终止条件和单层逻辑的配合如何站在父节点视角判断左叶子就是把单层逻辑想明白的典型。把这四道题放在一起横向对比会发现它们全都可以总结成一个统一的递归模板返回值 处理左子树 处理右子树 当前节点的贡献差别只在于处理的具体内容和当前节点贡献怎么算。222题当前节点贡献是1110题当前节点贡献是高度加1257题当前节点贡献是把节点值写入路径404题当前节点贡献是检查左孩子是否为左叶子并累加。6.2 遍历方式选择为什么这几道题都偏向后序一个非常明显的规律是222、110、404都用到了后序遍历的逻辑先处理左右子树再处理当前节点。原因很好理解这些题都需要先拿到左右子树的信息才能计算当前节点的结果。222要知道左右子树的节点数110要知道左右子树的高度404要知道左右子树各自包含的左叶子之和。257题是唯一使用前序遍历的因为路径的构造顺序要求先访问根节点再访问子节点和路径字符串的顺序完全一致。这个判断值得记一下什么时候用哪种遍历取决于当前节点的处理是否依赖子树处理结果。依赖就是后序不依赖而且要先输出当前节点就是前序。中序遍历在这四道题里没有特别的应用但在二叉搜索树题目里就会成为主旋律。6.3 迭代写法对比哪些递归改写迭代更舒服有些读者可能会好奇这四道题是否能用迭代写以及递归是否一定有劣势。事实是222题迭代层序计数非常自然代码甚至比递归更直观。110题迭代需要显式模拟后序遍历或者用栈记录每个节点的高度代码复杂度明显高于递归。257题迭代需要同时维护节点栈和路径栈两个栈逻辑稍绕但写出来之后对栈模拟递归的理解会加深不少。404题迭代层序或栈模拟都可以用父节点视角判断的逻辑和递归版本完全一致。我的建议是当前这个阶段优先把递归吃透迭代写法作为一种扩展练习。因为大部分复杂二叉树题目的标准解法都是递归迭代常常只是为了应对面试官追问你还能用其他方式实现吗。等递归成为一种本能反应之后再去补迭代写法性价比更高。7. 高频报错现场为什么写二叉树程序总报运行时错误7.1 最常见的元凶空指针解引用我还记得刚开始刷二叉树时经常被这样一个错误折磨程序在本地跑得好好的一提交就报Runtime Error也没说是哪一行。后来定位到原因绝大多数是空指针访问。特别是递归函数内部先访问了节点的左孩子或右孩子再判断是否为空。典型的错误写法长这样if (root-left ! nullptr) { ... } if (root-right-val ...) // 没判断 right 是否为空或者更隐蔽一点if (root-left root-left-left nullptr root-left-right nullptr) { sum root-left-val; }这个看起来没问题但如果root本身为空函数进来直接判断root-left就会崩溃。所以递归函数的第一行必须是空判断接下来所有对子节点的访问都要保证父节点存在或者像404题那样利用了短路特性把判空放最前面。另一个容易忽略的场景是递归终止条件不完整。比如有的同学写257题时只用root nullptr作为终止但没考虑当前节点是叶子的情况导致path里的内容在叶子处又继续向下递归访问了nullptr的left或right直接崩溃。递归终止条件和业务终止条件这两者有时候不是一回事必须想清楚。7.2 段错误还是栈溢出两种报错要分清二叉树递归写多了一个奇怪的现象本地跑小样例没问题一到大数据就段错误或者栈溢出。这通常不是空指针的问题而是递归深度过大。LeetCode默认递归栈深度足够支撑普通二叉树但如果树退化成一个超长的链条比如每个节点只有右孩子、没有左孩子那么递归深度就是节点总数。一棵几万甚至十几万层的链状树递归栈很容易爆掉。这里有个实用的排查办法出错后不要急着看算法先看报错类型。如果是Stack Overflow或者Segmentation Fault优先怀疑递归深度可以通过把递归改成迭代来验证如果是member access within null pointer这种信息优先怀疑空指针解引用。把这两类问题分开定位调试效率会高很多。7.3 自测时的一个好习惯手动画树再逐行走每次写完一道二叉树题在提交之前我会用纸笔画一棵三层左右的小树自己在脑内把递归过程走一遍。这个方法看起来很笨但真的能筛掉一大堆逻辑错误。比如110题画一棵左子树高度3、右子树高度1的三层树手动跑一遍代码马上就能发现单纯的左右子树高度差判断漏掉了子树本身是否平衡这个条件。又比如257题画一棵有两个叶子节点的树手动验证一下第二次递归时path是不是已经被正确回溯了。用这个习惯做自查比盲目反复提交黑盒测试要有效得多。等有了大概三五十道二叉树题的积累这个动作可以慢慢简化成只在脑内模拟但在初期阶段动手画图几乎是性价比最高的练习方式。8. 刷完这四道题我个人的一点心得四道题刷下来最深的感受是二叉树递归题的难点从来不是知不知道用递归而是想不想得清楚每一层递归在做什么。很多人在写222题时能写出遍历计数但问一句为什么这棵树可以直接用公式算节点数就卡住了写110题时只知道用高度函数但意识不到重复计算的问题写257题时知道要维护一个path却没想明白为什么递归返回后要把它弹掉。这些问题都说明一件事对递归过程的心智模拟还不够熟练。我自己的方法是在刷题笔记里把每一道题都拆成三个问题来记录第一个是递归函数的参数和返回值分别是什么第二个是终止条件是否对所有边界情况有效第三个是单层递归逻辑里哪些操作是处理当前节点、哪些是向子树传递状态、哪些是递归返回后必须做的还原。这套模板用熟了之后再看到新题就能比较快地定位到考点这题考的是返回值设计那题考的是状态回溯。跳出来看这四道题本身都不算难难度在LeetCode上也就是easy到medium的水平。但如果能把它们彻底吃透后面遇到求树的直径、判断对称二叉树、序列化与反序列化二叉树这类题就能明显感觉到自己有了应对的底气。刷题这个东西慢就是快把这四道题里暴露出来的每一个为什么都研究明白后面省下来的时间远不止四道题的量。