刷到代码随想录算法训练营第15天正好是我感觉自己二叉树基础题开始“不够用”的时候。这一天安排的四道力扣题——110平衡二叉树、257二叉树的所有路径、404左叶子之和、222完全二叉树的节点个数——把递归里最容易含糊的几个点全给点了一遍返回值怎么设计、回溯什么时候发生、叶子节点的定义怎么抠、完全二叉树性质如何变成复杂度优势。如果你正跟着训练营在刷或者二叉树基础题已经过完、想在递归和回溯上再扎实一点的这篇可以当一份很干的刷题笔记用。1. 第15天任务拆解四道题到底在练什么1.1 四道题的定位与难度梯度这四道题按题号排是110、257、404、222但按内容分其实覆盖了二叉树递归的四种典型流派。我先把它们的定位和难度体感列成一张表后面再逐个拆。力扣题号题型核心考点难度体感110 平衡二叉树后序遍历递归返回值设计子树高度与平衡状态同时维护中等257 二叉树的所有路径前序遍历回溯路径收集撤销选择中偏难404 左叶子之和递归遍历左叶子的定义在父节点判断简单222 完全二叉树的节点个数递归满二叉树剪枝完全二叉树性质位运算中偏难单看每一道题都是二叉树的遍历但把它们放在同一天练训练营的意图其实很明确逼你把递归函数的职责想清楚。110要把子树的高度“送上来”257要把路径上的节点“带下去”404要判断当前节点和左孩子的关系222则是利用整棵树的结构性质直接跳过一整棵子树的遍历。四种递归节奏放在一起比连续刷十道同类题更能刺激思考。这四道题还有一个共同点都可以用暴力写法AC。110可以每个节点重新求高度257可以用字符串传值免去回溯404可以加isLeft参数222可以层序遍历计数。但暴力写法往往正好绕开了考点这也是为什么很多人AC了还是觉得没学到东西。1.2 我推荐的刷题顺序与节奏我实际刷的时候没有按题号来而是按难度递增先做404左叶子之和因为它最简单用来热手很合适再做110平衡二叉树巩固后序遍历然后做257所有路径这一题要花时间把回溯想透最后做222完全二叉树的节点个数它最硬核需要完全二叉树的性质做剪枝。按这个顺序每道题的心智负担是慢慢加重的。如果你一上来就啃222很容易被位运算和满二叉树性质劝退。时间预算上404大约15分钟110大约25分钟257大约40分钟222大约45分钟整体两小时上下。超时特别正常尤其是257第一次接触回溯的时候卡一个小时不丢人。每道题我都要求自己先不看题解想十分钟想不出来再看答案然后关掉答案手写一遍。这个流程对“刷完就忘”非常有效因为你看懂答案只是输入自己重新写一遍才是输出。2. 逐题拆解从题意到递归设计的完整思路2.1 力扣110 平衡二叉树递归返回值比你想的更重要题目给一棵二叉树判断它是不是高度平衡的二叉树。平衡的定义很关键每个节点的左右子树高度差不超过1。注意是每个节点不是只有根节点。为什么不能用先序遍历因为判断一个节点是否平衡需要它的左右子树高度而高度只能自底向上算天然就是后序遍历才能拿到的信息。先序遍历只能从上往下判断根节点根本不知道子树内部平不平衡。递归设计思路是这样写一个getHeight(node)函数返回以node为根的子树高度如果发现这棵子树已经不平衡就返回-1作为哨兵。空节点高度记0。求左子树高度如果已经是-1直接返回-1说明左子树不平衡整棵树不可能平衡可以提前剪枝右子树同理。最后比较左右高度差大于1就返回-1否则返回max(left, right) 1。为什么用-1而不是返回bool再单独搞一个全局变量记录高度因为递归返回值在每一层是独立的全局变量会被层层覆盖父节点根本拿不到子树的真实高度。用一个int同时承载“这棵子树多高”和“是否平衡”两个信息是最内聚的写法。很多初学者写110跑不对就是掉进了“递归里想用bool又想传高度”的坑。举个例子根节点1左子树22的左孩子4没有右子树。单看根节点左子树高度2右子树高度0差为2已经不平衡。但即使根节点左右差等于1子树内部也可能已经差了2所以必须后序遍历到底。这个例子说明“根节点平衡”不等于“整棵树平衡”。2.2 力扣257 二叉树的所有路径回溯就藏在递归的往返之间题目要求返回所有从根节点到叶子的路径输出形如[1-2-5, 1-3]。解法用前序遍历先处理当前节点把它推进一个路径容器path里如果当前节点是叶子就把path转成字符串放进结果集否则分别递归左右孩子递归返回后要从path里把当前节点pop掉。这个pop操作就是回溯。我习惯用一个生活类比在岔路口用铅笔在本子上记路线走到死路返回岔路口时必须把刚才那条路的记录擦掉才能继续记下一条。如果不擦第二条路就会带着前一条路的残影最后输出的路径全是串线。为什么推荐用vectorint path而不是直接用string传值因为string按值传递时每次递归都会拷贝一份旧字符串根本没被修改隐式实现了“撤销”但代价是让初学者误以为回溯是自动发生的。vectorint path是真正的共享引用递归返回后必须手动pop_back才能逼你关注回溯的时机和位置。贴一个容易踩的实现细节不要在叶子节点提前return然后指望调用处pop这样代码里会出现两处pop、对称性很差。更稳的写法是无论叶子还是非叶子都在递归函数末尾统一pop_back。下面这份代码是我推荐的样子。class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root ! nullptr) { traversal(root, path, result); } return result; } private: void traversal(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); if (node-left nullptr node-right nullptr) { result.push_back(pathToString(path)); } else { if (node-left) traversal(node-left, path, result); if (node-right) traversal(node-right, path, result); } path.pop_back(); } string pathToString(const vectorint path) { string s; for (int i 0; i path.size(); i) { if (i 0) s -; s to_string(path[i]); } return s; } };这个版本里叶子节点也会走到最后的pop_back所以递归返回时path一定恢复原状逻辑对称、不容易漏。2.3 力扣404 左叶子之和在父节点上做判断才干脆题目要求计算所有左叶子节点值的和。左叶子的定义要抠字眼它是父节点的左孩子并且它自己没有左右孩子。很多人第一反应是递归遍历所有节点遇到叶子再判断“我是不是左孩子”。但递归函数默认只拿到当前节点并不知道自己在父节点眼里是左还是右除非给递归函数额外传一个bool isLeft参数。这种方案能做但代码会绕而且容易把状态传错。更简洁的方案是在父节点位置做判断。递归到node时检查node-left如果它不为空且它的左右孩子都为空那么node-left就是一个左叶子直接累加。然后继续递归左子树和右子树。这里有一个必须强调的坑不能只递归左子树就return。因为右子树内部也可能有左叶子。比如根节点只有右孩子3右孩子3又有一个左孩子44就是左叶子必须通过递归右子树才能加到。所以即使当前节点的左孩子是叶子也要继续递归它只不过它的左右子树都为空递归返回0不会重复计数。核心代码逻辑可以浓缩成一句话先判断“当前节点的左孩子是不是叶子”是就加上然后无条件递归左右子树。这个思路在代码里非常清爽。2.4 力扣222 完全二叉树的节点个数用满二叉树性质做剪枝完全二叉树的标准定义是叶子节点只能出现在最下层并且最下层的叶子节点连续集中在左侧。求节点总数最简单的做法是遍历整棵树递归或层序都能过但时间复杂度是O(N)。这道题的进阶考点是利用完全二叉树性质做到O(logN * logN)。核心观察是满二叉树的节点数可以直接用深度算一棵深度为d的满二叉树节点数是2^d - 1这里的d按“最左侧路径节点数”定义单节点深度为1。那么只要能判断出某棵子树是满二叉树就不用遍历它直接套公式。怎么判断写一个getDepth(node)从node出发一路沿着左孩子走统计最左侧路径的节点数代价是O(logN)。对根节点分别算左子树和右子树的最左侧深度。如果两者相等说明左子树必然是一棵满二叉树。原因很简单完全二叉树从左到右填充右子树能到达同一深度左子树不可能还缺节点。此时左子树节点数直接用2^leftDepth - 1算根节点再加1所以根节点的左子树加上根节点合计2^leftDepth然后递归算右子树。如果两者不相等那么一定是左深度比右深度多1并且右子树是满的。此时根节点加上右子树合计2^rightDepth然后递归算左子树。这个性质可能反直觉但画棵树逐层填充就能理解完全二叉树的层内连续性决定了“右侧到达的深度”就代表这一层已经填满。位运算要注意1 leftDepth就是2的leftDepth次方。在上面两个分支里这个值表示的分别是“左子树根”或“右子树根”的节点数千万不要随手再减一。我建议提交前先手推三个用例只有根节点、根带一个左孩子、根带左右两个孩子确保公式没写反。3. 实操代码实现递归三要素与四份可直接复用的代码3.1 动手前先回答三个问题写任何二叉树递归题写代码前先口头回答三个问题递归函数返回什么终止条件是什么单层逻辑处理什么把这四道题对齐到这三个问题就能得到一张非常直观的表格。题目递归返回终止条件单层逻辑110子树高度-1表示不平衡空节点返回0求左右高度检查差值是否大于1257void结果由result收集叶子节点拼接路径push入path递归左右pop出path404左叶子之和空节点返回0判断左叶子递归左右累加222子树节点数空节点返回0比较两侧深度按分支递归这张表填完代码基本就是填空了。很多人写递归卡住不是不会语法而是没想清楚“这个函数到底要向上层返回什么信息”。110返回高度和平衡状态222返回节点数这两个是典型的数值型递归257和404则是把结果放在外部的result或累加变量里递归函数本身不返回业务值。分清楚这两种模式能少踩一半的坑。3.2 完整实现C与Python对照下面把四道题的可提交版本都贴出来。C版默认力扣环境已经引入标准库如果要在本地编译110需要包含cstdlib或cmath。110平衡二叉树的C实现class Solution { public: bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } private: 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; } };110的Python实现from typing import Optional class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: def height(node): if not node: return 0 left height(node.left) if left -1: return -1 right height(node.right) if right -1: return -1 if abs(left - right) 1: return -1 return max(left, right) 1 return height(root) ! -1257所有路径的C实现class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root ! nullptr) { traversal(root, path, result); } return result; } private: void traversal(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); if (node-left nullptr node-right nullptr) { result.push_back(pathToString(path)); } else { if (node-left) traversal(node-left, path, result); if (node-right) traversal(node-right, path, result); } path.pop_back(); } string pathToString(const vectorint path) { string s; for (int i 0; i path.size(); i) { if (i 0) s -; s to_string(path[i]); } return s; } };257的Python实现这里用字符串直接拼接隐式实现了回溯代码更短from typing import Optional, List class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]: result [] if not root: return result def dfs(node, path): if not node.left and not node.right: result.append(path) return if node.left: dfs(node.left, path - str(node.left.val)) if node.right: dfs(node.right, path - str(node.right.val)) dfs(root, str(root.val)) return result404左叶子之和的C实现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; } sum sumOfLeftLeaves(root-left); sum sumOfLeftLeaves(root-right); return sum; } };404的Python实现from typing import Optional class Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) - int: if not root: return 0 total 0 if root.left and not root.left.left and not root.left.right: total root.left.val total self.sumOfLeftLeaves(root.left) total self.sumOfLeftLeaves(root.right) return total222完全二叉树节点数的C实现class Solution { public: int countNodes(TreeNode* root) { if (root nullptr) return 0; int leftDepth getDepth(root-left); int rightDepth getDepth(root-right); if (leftDepth rightDepth) { return (1 leftDepth) countNodes(root-right); } else { return (1 rightDepth) countNodes(root-left); } } private: int getDepth(TreeNode* node) { int depth 0; while (node ! nullptr) { depth; node node-left; } return depth; } };222的Python实现from typing import Optional class Solution: def countNodes(self, root: Optional[TreeNode]) - int: if not root: return 0 def depth(node): d 0 while node: d 1 node node.left return d left_depth depth(root.left) right_depth depth(root.right) if left_depth right_depth: return (1 left_depth) self.countNodes(root.right) return (1 right_depth) self.countNodes(root.left)3.3 复杂度实测对比写完之后一定要有复杂度意识。这道题很多人AC了但说不清复杂度面试基本就穿帮了。题目时间复杂度空间复杂度核心一句话110O(N)O(H)-1哨兵同时传高度和不平衡状态257最坏O(N^2)O(H) 结果空间字符串拼接是主要成本404O(N)O(H)父节点判断左叶子222普通解法O(N)O(H)遍历所有节点222优化解法O(logN * logN)O(logN)满二叉树剪枝只进一边257为什么最坏是O(N^2)因为每个叶子路径的长度和树高相关输出结果本身的长度就有O(N * H)。C用to_string拼字符串时还会不断拷贝树退化成链表的时候尤其明显。不过力扣正常数据下不会触发极端情况。222优化版的复杂度值得多说一句每次countNodes只会递归进入其中一侧子树但每次进去之前都要算两个getDepth每个getDepth是沿着最左侧走代价O(logN)所以总体是O(logN * logN)。空间复杂度是递归深度O(logN)。在节点数接近10^9的大完全二叉树上普通遍历要秒级优化解法是毫秒级。4. 容易踩的坑与调试技巧实录4.1 返回值设计和全局变量的分工错误110最常见的错误就是递归函数返回bool然后在递归里试图用成员变量记录高度。这样做的结果是递归返回后高度变量被上层覆盖父节点根本拿不到子树真实高度判断就全乱了。要么用哨兵int返回高度要么额外维护高度表前者明显更干净。257最常见的错误是忘记pop_back输出结果出现“1-2-5-3”这种串线路径。另一个错误版本是在叶子节点提前return然后在调用处补一个pop结果逻辑东一榔头西一棒子很难查。我推荐统一在函数末尾pop这样每个节点“推进去一次必然弹出来一次”对称性是最好的。404的经典错误是把“左子树的叶子”误当成“左叶子”只递归左子树然后return完全丢掉右子树里的左叶子。还有人在叶子节点试图判断自己是不是左孩子然后发现递归函数根本不知道这个信息只能加参数绕弯。222的经典错误是直接把完全二叉树当成满二叉树上来就返回2^depth - 1。完全二叉树只有在每一层都满的时候才等于满二叉树所以必须加左右深度相等的判断。另一处是位运算写反1 depth里的depth和“最左侧路径节点数”的定义要保持一致我自己第一次写的时候就在相等分支里多减了一个1。4.2 边界条件自查清单刷完AC之后至少用下面这些边界用例自查一遍能过滤掉大部分隐藏问题空树110返回true257返回空列表404返回0222返回0。单节点110返回true257输出[1]404是0因为根节点不算左叶子222是1。左单链1-2-4110应该返回false因为节点1的左右子树高度差是2。根节点只有右孩子右孩子又有左孩子404的左叶子之和要能算出来这是最容易被漏掉的情况。完全二叉树但不完整比如[1,2,3,4]222优化解法要能算出4不能误判成满二叉树。特别是222建议把用例[1,2,3,4]和[1,2,3,4,5,6]都手推一遍。前一个会走“左右深度不等→右子树满”的分支后一个会走“左右深度相等→左子树满”的分支。两个分支都验过代码基本就稳了。4.3 调试小技巧打印法定位回溯误区二叉树递归题最通用的调试手段是打印递归进入和退出的信号。以257为例在traversal入口打印当前节点值和path大小在pop_back之后打印退出时的path大小。如果发现退出时path大小比进入时大说明某次递归漏了pop输出的路径就必定串线。110可以在getHeight里打印每个节点返回的高度找到第一个-1出现的位置就能快速定位是哪棵子树先不平衡比盯着空荡荡的编译器报错强得多。222可以在countNodes里打印leftDepth和rightDepth观察满二叉树判断的分支是如何生效的。我调试时的习惯是先用小用例验证公式再随机构造一个5层左右的完全二叉树肉眼验证节点数结果。递归的问题用打印法基本都能在几分钟内定位。说实话我不是那种一次就能把四道题全部通过的选手。257第一次写就忘了pop_back多跑了几遍才把“递归返回时擦掉选择”这个动作刻进肌肉记忆。后来刷二叉搜索树、回溯子集和排列问题时才发现训练营第15天安排的这几个题反复在练同一件事设计好递归的返回值看清递归的往返时机。如果你今天刷到这四道题觉得吃力很正常。多花一点时间把每道题用两种写法各做一遍比草草AC四道题更有意义。