二叉树刷题进阶：四道经典题吃透递归与回溯

第十五天，算法训练营刷到二叉树的中段。LeetCode 110、257、404、222这四道题排在一起，标着难度分别是简单、简单、简单、中等，但把它们当成一套组合题来刷，你会明显感觉到这一阶段和前面十天刷遍历时的差别：题目开始要求你带着目的去递归了。平衡二叉树考你对高度的理解方式和剪枝设计，二叉树的所有路径是回溯的第一次正面接触，左叶子之和逼着你换一个视角看树，完全二叉树的节点个数则是利用数据结构性质做复杂度优化的典型。这篇文章把四道题从头到尾拆开讲，包含完整思路、可运行的代码、复杂度推导和我在实际练习中踩过的坑，给同样在刷这组题的朋友做个参照。

1. 第十五天的题量安排与知识定位

1.1 从“遍历”到“解题”的关键转换

前面的训练内容基本上围绕四种遍历方式展开：前序遍历、中序遍历、后序遍历、层序遍历，再加上几道经典递归题，比如求最大深度、最小深度、判断对称树。到第十五天，题目难度并没有突然拔高，但考点变了——不再仅仅要求你把树完整走一遍，而是要求你在遍历过程中做筛选、做记录、做汇总。比如所有路径要求在遍历时保存一条完整的链，左叶子之和要求在遍历时筛选满足特定条件的值，完全二叉树的节点个数要求你不遍历也能算出数量。这种从“访问所有节点”到“带着业务条件访问节点”的转变，是二叉树刷题的第一个分水岭。

很多人在这几天会有一种错觉，觉得题都见过、套路都熟悉，结果一提交就漏洞百出。原因其实就是前面的遍历题太“安全”了，递归写好基本就过了，而这四道题需要你在递归返回值、终止条件、状态恢复这些细节上做设计，稍有不慎，逻辑就对不上。

1.2 四道题互相补充的知识模块

110平衡二叉树的核心是递归返回值的双用：既要返回子树高度，又要标记是否失衡。257的核心是回溯和路径记录。404玩的是视角转换，站在父节点去判断左叶子。222则考验性质挖掘，利用完全二叉树左右子树高度关系把规模减半。四道题覆盖了递归设计的三个层面：返回什么、什么时候收手、怎么消除向上传递的副作用。把它们放到同一天练，比单独刷效果更好，因为你会在四道题之间看到同一套递归思维的四种变体，这种对比带来的理解深度，是单刷十道同类题也换不来的。

1.3 难度评价中的陷阱

LeetCode 上110、257、404都标为简单，但绝大多数第一次刷的人都会卡在细节上。110容易在终止条件上写错，257容易在回溯时忘掉移除节点，404容易把自己绕进“左子树里的叶子”这句话。真正刷下来你会发现，难度标签只能说明思考路径不长，不代表实现没有坑。这套题的实操时间我建议按1.5小时到2小时来安排，宁可把代码写慢一点，把每一处的递归返回值含义写注释，也不要赶进度。后面刷路径总和、构造二叉树这类题时，你会回来感谢这天的慢。

2. LeetCode 110 平衡二叉树：一次后序遍历完成判断

2.1 题目本质与暴力思路的问题

平衡二叉树的定义是：每个节点的左右子树高度差不超过1。注意是每个节点，不是只看根节点。要在根节点判断整棵树是否平衡，就必须先知道左右子树是否平衡；而要判断左右子树是否平衡，又得知道更下面子树的信息。这天然适合递归。

最容易想到的思路是自顶向下：对于一个节点，先分别计算左右子树的高度，比较差值；然后递归判断左子树和右子树是否平衡。这个做法是正确的，但效率很差。计算高度本身是递归遍历，而外层又在每个节点上重复计算一次高度。以一条链为例，计算每个节点的高度都要走到叶子，总时间大约是O(n^2)。我在本地用长度为1000的链测过，暴力解法明显慢几个量级，在LeetCode上虽然也能过，但属于碰运气。真正面试的时候，这种解法大概率会被追问一句“能不能优化”。

2.2 后序遍历的高度与-1哨兵

自底向上的方式只需要一遍遍历。既然是先知道左右子树的结果，再决定当前节点怎么处理，自然选择后序遍历。

这里的关键设计是：递归函数返回什么？常规思路是返回当前子树的高度。但还有一类需求是“这棵子树不稳了，赶紧往上报”。因为合法高度永远是非负整数，用一个负数当哨兵完全可行，-1就是最常用的。于是递归逻辑变成：左子树返回-1说明左子树不平衡，直接返回-1；右子树同理；左右都平衡再检查高度差；最后返回当前节点高度，也就是左右较大者加1。

用-1做哨兵的好处是省掉一个额外布尔标记，判断条件也会简单。缺点是它依赖“高度不可能为负数”这个约定，看代码时需要知道这个隐式规则。如果你更在意可读性，也可以返回一个二元组，比如(is_balanced, height)，但在递归深度栈上会多占一点空间，而且判断语句会更啰嗦。我平时写题用-1，写工程代码用二元组，看场景决定。

class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def dfs(node): if not node: return 0 left_height = dfs(node.left) if left_height == -1: return -1 right_height = dfs(node.right) if right_height == -1: return -1 if abs(left_height - right_height) > 1: return -1 return max(left_height, right_height) + 1 return dfs(root) != -1

2.3 代码的边界与易错点

第一个易错点是终止条件。空节点的高度是0，这个必须写在最前面。有人会写成返回True或者False，那整个递归的返回值类型就乱了。第二个易错点是递归返回的数值含义。有人会写成“返回左右子树的节点数之差”，把高度差和节点数差混在一起，这在某些测试用例下会得到错误答案，因为平衡定义用的是高度，不是节点多少。第三个易错点是剪枝时机：左子树已经不平衡时，右子树就不用再跑了，直接返回-1。这样可以省掉一半甚至更多的递归调用，对不平衡的大树提速非常明显。

我见过一种写法是先用一个全局变量记录是否平衡，然后照常递归遍历整棵树。这种写法也能过，但不够干净。既然递归函数本身就能把不平衡状态传上去，就不需要额外维护一个外部状态，少一个变量就少一份出错的可能。

2.4 手写验证的测试用例

我建议本地至少跑这样几组：空树返回True；单节点返回True；根节点左右高度差为2的三层树返回False；链式结构“左右交替”的不平衡树返回False；以及题目示例中那个经典的[1,2,2,3,3,null,null,4,4]，这个用例能有效查出错把“子树平衡”当“整棵平衡”的写法。为什么特意提这个用例？因为它前面的节点都满足高度差为1，只有到了第四层才暴露失衡，很多粗心的实现会在这一层挂掉。

3. LeetCode 257 二叉树的所有路径：回溯与路径收集

3.1 为什么路径题要用前序遍历

输出要求非常明确：从根到每个叶子的完整路径，用箭头连接。这里不能后序遍历，因为你收集路径时需要知道“当前走到了哪个节点”。前序遍历的顺序是“先处理当前节点，再进入子树”，这样路径列表天然就是根到当前节点的顺序。你可以尝试中序或者后序，会发现收集到的路径要么顺序错乱，要么需要额外反转，很别扭。

说白了，路径是“根先出发，一路往下”的记录，只有前序遍历贴合这个语义。这类题后面还会以各种形式出现，比如求根到某个目标节点的路径、求路径总和等，套路都一样，前序遍历加上回溯。

3.2 回溯的本质：走到头要退回来

计算机在递归时只知道往下走。当递归返回时，路径列表如果不做处理，就会保留着访问过的节点，导致下一分支的路径里混入上一分支的记录。想象成走迷宫时手里拿一根绳子，进入新岔路时绳子放长一截，退回来时必须把放长的绳子收回，否则下一次走的路径就会被这根多余的绳子污染。在递归实现里，“放长绳子”是对应的path.append(...)，“收回绳子”是path.pop()。两个操作必须成对出现，写在同一个递归函数里。

很多人第一次接触回溯会觉得抽象，其实核心就是这一句话：递归前做了什么，递归返回后就要撤销什么。不撤销的话，状态是叠加的，后面的分支都会拿到脏数据。这题练的就是这个基本功。

3.3 两种常见的递归写法对比

第一种是共享路径列表加显式回溯：

class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: res = [] if not root: return res def dfs(node, path): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append("->".join(path)) else: dfs(node.left, path) dfs(node.right, path) path.pop() dfs(root, []) return res

第二种是每次传入新的列表副本，不需要pop：

class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: res = [] def dfs(node, path): if not node: return new_path = path + [str(node.val)] if not node.left and not node.right: res.append("->".join(new_path)) return dfs(node.left, new_path) dfs(node.right, new_path) dfs(root, []) return res

两种写法都能过。区别在于空间：显式回溯版共用一份路径列表，递归深度是树的深度h，额外空间O(h)；传值拷贝版在每一层都复制一遍列表，对于一条链来说会产生O(n^2)的累计空间。第一种写法理解成本略高，但它才是回溯的一般形态。后面做路径总和、组合、排列这些题，全都依赖“共享状态加显式回退”这套模式，所以我在训练营第十五天建议直接把第一种写法练熟。

3.4 细节：什么时候收获结果

路径题最怕的错是在不该收获的时候收获。收获结果的唯一条件：当前节点是叶子，也就是左右孩子都为空的节点。注意，不要再往叶子下面递归了。在有显式回溯的版本里，我把append放在递归入口处，这样根节点也会被加入路径；然后判断叶子，叶子就生成结果；非叶子就走左右孩子；最后统一pop。这样所有分支的路径都正确。还有一种写法是：进入节点时先判断空，再判断叶子，再分别递归左右，逻辑一样，只是pop的位置要注意别漏掉。

另有一个边界：如果二叉树为空，直接返回空列表。如果只有根节点，路径是“1”，这正好对应叶子判断才收获结果的逻辑，不需要额外特判。写过递归的人应该都有体会，特判加得越多，代码越容易出乱子，能靠逻辑本身覆盖的边界就别手工处理。

4. LeetCode 404 左叶子之和：换个视角看叶子

4.1 “左叶子”到底是什么

左叶子是指“是左孩子、并且本身是叶子”的节点。一个节点是叶子，意味着它没有孩子；它还得是别人的左孩子。这里有个天然的信息不对称：你站在一个节点上，只能看出它自己是不是叶子，但看不出它在父节点眼中是左还是右。所以解题必须换一种思路：站在父节点这边，检查“我的左孩子是不是一个叶子”。

很多人看到“左叶子”这三个字会条件反射去找整棵树偏左的节点，然后越写越乱。关键是要把判定条件写清楚：存在左孩子；左孩子没有左右儿子；满足这两个条件时，左孩子的值就是贡献值。注意，贡献的值是左孩子的值，不是父节点的值，也不是左右子树返回值的简单相加。这个细节看似废话，但提交记录里写错的人真不少。

4.2 递归设计：在双层判断中累加

递归遍历整棵树，在每个当前节点判断一次：如果当前节点的left存在且left的左右孩子都不存在，把left.val加入结果。然后继续递归left和right。这个设计的好处是视角一致，每个节点都负责判断自己的左孩子，递归下去覆盖整棵树。

写法上要注意，不能只把递归结果return掉。例如：

class Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: if not root: return 0 ans = 0 if root.left and not root.left.left and not root.left.right: ans += root.left.val ans += self.sumOfLeftLeaves(root.left) ans += self.sumOfLeftLeaves(root.right) return ans

这个函数返回的是“以当前节点为根的子树的左叶子之和”。每一层都先处理自己这一层的左叶子判断，再叠加左右子树的递归结果。递归的返回值设计比较直观，不会有歧义。

4.3 另一种带标记的写法

除了站在父节点判断，也可以给递归函数加一个isLeft参数，表示这个节点是不是作为左孩子被访问到。叶子节点且isLeft为True时，返回它的值；其他情况继续递归。这种写法好处是思路直观，不需要在每个函数里额外判断“父节点的左孩子是否为叶子”，坏处是递归调用多了一层参数，且对空节点、根节点等边界情况要多加小心。我个人比较推荐第一种写法，但它确实没有第二种写法那样容易一眼看明白，所以我把两种都放在这里对比，读者可以选一种练习。

从训练营的角度讲，第二种写法适合用来理解“递归参数不只是节点本身，还可以带上额外的上下文信息”这件事，后面做路径总和、二叉树的序列化等题目时，这种带附加参数的递归很常见。

4.4 这题最容易被忽略的测试用例

根节点也算吗？不算。如果根节点没有父节点，它不是任何人的左孩子。例如只有根节点的树，答案是0。又例如[3,9,20,null,null,15,7]，9是左叶子，7不是，答案是9，这个用例能检查你有没有把左子树的叶子全部算进去。还有一个容易出错的用例是[1,2,3,4]，4是左叶子，它的父节点2不是叶子，所以2本身不能贡献，但需要在递归2时判断出4这个左叶子。

其实这题真正想考的不是“会不会遍历”，而是“会不会从父节点视角看问题”。只要理解到这一层，代码基本不会写错。

5. LeetCode 222 完全二叉树的节点个数：把性质变成复杂度优势

5.1 普通解法的复杂度瓶颈

最直接的写法，数节点就是递归遍历一遍：

class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if not root: return 0 return 1 + self.countNodes(root.left) + self.countNodes(root.right)

这是标准答案吗？是正确答案，但时间O(n)、空间O(h)。如果树有千万个节点，这就是千万次递归调用。题目没说节点数量级，但既然专门考“完全二叉树”，显然希望你不要满足于这个通用解。

有人会觉得，O(n)已经很快了，为什么要优化？因为完全二叉树是一种非常特殊的结构，它的形状是确定的，一定可以靠公式算出一大部分节点数。当数据量级达到很大时，O(log^2 n)和O(n)的差距是数量级的。面试场合写这段优化代码，明显比直接遍历更能体现你对数据结构的理解。

5.2 完全二叉树的两个关键性质

完全二叉树有一个决定性特征：除了最后一层，上面的所有层都是满的；最后一层的节点都靠左连续排列，不会出现右边有节点而左边空缺的情况。由这个特征可以推出一个重要结论：从根节点出发，左子树的高度要么等于右子树的高度，要么比右子树多1。不可能出现左子树比右子树矮的情况。

如果左子树高度等于右子树高度，说明最后一层已经延伸到了右子树，那么左子树一定是满的。如果左子树高度比右子树多1，说明最后一层只铺到了左子树范围，右子树一定比左子树矮一层，此时右子树整层是满的。这就是判断“哪边是满的”的依据。

这两个性质理解清楚了，代码逻辑就顺了。核心思想一句话：每次确认一半子树是满的，用公式直接算，剩下一半递归往下算。

5.3 满子树节点数用位运算直接算

高度为h的满二叉树节点数等于2^h - 1。如果左子树满且高度为dl，那么“左子树 + 根节点”的节点数是2^dl，也就是1 << dl。剩下的另一边继续递归算。同理，右子树满且高度为dr时，先加上“右子树 + 根节点”的节点数1 << dr，再递归算左子树。

为什么不用内置的pow或**？因为位移运算不调用浮点库，速度更快，在算法题里也更直观。遇到2的幂优先写1 << n，已经是刷题圈里的常见习惯。注意运算符优先级，1 << dl和1 << dr都要加括号吗？看你的写法，如果在表达式里混着加减，建议加括号，避免写成1 << dl + 1这种被解析成1 << (dl + 1)的坑。

5.4 完整实现与复杂度推导

class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: def get_depth(node): depth = 0 while node: node = node.left depth += 1 return depth if not root: return 0 left_depth = get_depth(root.left) right_depth = get_depth(root.right) if left_depth == right_depth: return (1 << left_depth) + self.countNodes(root.right) else: return (1 << right_depth) + self.countNodes(root.left)

每次递归规模减半：深度差为0时，递归算右子树，规模约为n/2；深度差为1时，递归算左子树，规模也约为n/2。每层递归调用get_depth需要沿着左边界走到最底，完全二叉树的高度是O(log n)，所以每层代价O(log n)。一共O(log n)层，总时间O(log^2 n)。这个优化在n大时优势明显，比如节点数大约100万，O(n)要做约100万次运算，O(log^2 n)大概只有400次左右。

5.5 边界与陷阱

这里的else分支实际上覆盖了left_depth > right_depth的情况。严谨地说，完全二叉树不会出现left_depth < right_depth，但简单写else也没毛病，能处理异常输入。另外，get_depth必须一直沿左孩子走。有人会把“当前节点向右子树延伸几次”当成高度，那是完全不同的含义。

用位运算还有一处细节：当子树高度为0时，1 << 0等于1，代表“根节点自己”，数值是对的。这个边界值得注意，避免写成1 << depth + 1这样括号错位的式子。我在本地调试时特意跑了一个单节点用例，确认递归能正常返回1才提交。

6. 四道题串起来的三个方法论

6.1 递归函数返回值决定一切

四道题写完后你会发现，递归函数“返回什么”是最重要的决策。110返回子树高度，用-1表示失败；257的递归不返回值，只修改外部结果；404返回左叶子之和；222返回子树节点个数。返回值设计好了，整个逻辑就顺了；返回值得含糊，后面全在打补丁。一个实操建议：动笔前先把注释写上，比如“返回以node为根的子树高度，若不平衡则返回-1”，然后再写递归主体。我在第7章还会专门说这个习惯，因为它真的是我刷题效率提升的关键。

6.2 前序和后序怎么选

判断顺序的直觉：边往下走边做决策的，比如收集路径、找目标路径，用前序；需要先知道子问题的答案再汇总的，比如判断子树是否平衡、计算子树节点数、统计子树里的左叶子，用后序。404是例外，它用前序也行，因为每个节点只做判断不依赖子结果，但我采用自顶向下的写法是因为判断条件在父节点。判断顺序的核心原则是：父节点需要什么信息，就决定在什么时候访问子节点。

如果把这个问题想透了，后面做二叉树的最近公共祖先、最大路径和这类题时会省很多力气。那些题的本质就是“我需要子节点给我什么信息，然后我怎么处理”。

6.3 刷题节奏和手感养成

这一天的题量其实不小，我建议采用“两遍过”的策略：第一遍只看题目自己憋半小时，卡住了看题解思路，然后默写代码；第二遍合上题解，直接在白板上写完整实现，跑测试用例。不要只做一遍就觉得完事了。第二遍才是真正把递归返回值、回溯时机、复杂度推导这些细节刻进肌肉记忆的时刻。第十五天还是能把四道题控制在两个小时内的，这个节奏对于后面刷路径总和、构造二叉树这类更复杂的题目，会很关键。

7. 我踩过的坑：常见错误排查与一个小技巧

7.1 四道题的高频错误速查表

这张表是我实际刷题过程中一条条记下来的，不是凭空总结。刷到后期我还会偶尔返回来翻，尤其是每次写回溯题卡住的时候，看看257这一行，提醒自己append和pop要成对。

7.2 本地调试专用工具：层序转数组

刷二叉树的题，最烦的就是一把测试用例眼睛看不出来对错。我习惯写一个把二叉树转成数组的小工具做对比，层序输出，末尾的空节点去掉再打出来。比如[1,2,2,3,3,null,null,4,4]这样的用例，直接打印树的层序数组，一眼就能看出来结构是不是自己想要的。这个工具在验证110、257这几道题时非常好用。

代码核心就十几行，队列做层序遍历，遇到空节点记录None，最后修剪末尾的空值。如果你也在刷链式结构，强烈建议先把这个工具放进自己的代码片段里。本地调试的效率提升非常明显，尤其当你在递归里改来改去的时候，有一个能可视化树结构的工具，比猜错强太多。

我这里也顺手分享一个简单版本：

def tree_to_list(root): if not root: return [] res = [] q = [root] while q: node = q.pop(0) if node: res.append(node.val) q.append(node.left) q.append(node.right) else: res.append(None) while res and res[-1] is None: res.pop() return res

7.3 一个改变我写递归习惯的提示

我后来养成了一个很小的习惯：递归函数的开头不先写代码，而是先写一句话注释，说明这个函数返回什么、什么时候停止。比如“返回以node为根的子树高度，若失衡返回-1”。写注释的过程倒逼我把语义想清楚，很多写着写着发现逻辑矛盾的情况都被这个习惯避免了。训练营第十五天之后我刷题效率明显变高，这个注释习惯比任何技巧都管用。

尤其是在110这种“返回值同时承担多种语义”的题目里，不写注释特别容易乱。你回头看一眼自己三天前写的递归代码，如果还需要想半天才明白返回值是什么，那说明当时注释没写够。把语义钉死在注释里，调试和复习都会轻松很多。

这四道题刷完之后，我个人最大的体会是：二叉树递归的瓶颈从来不是语法，而是“有没有想清楚每一层递归到底在做什么”。想清楚了，代码自然就顺了。哪怕过了很久再回头看，注释和结构都还在，复习成本也很低。如果你今天正卡在某一题上，不妨先停下来，把返回值注释写出来，再往下走。