刷 LeetCode 刷到二叉树这一块很多人会出现一种“似懂非懂”的状态遍历顺序背得滚瓜烂熟一写递归就大脑空白尤其碰上“完全二叉树”“平衡二叉树”“所有路径”“左叶子之和”这种词四个题放一起更是头皮发麻。这篇就是来把这四道题彻底讲透的。它们正好是二叉树递归的四个经典侧面数节点、判平衡、收路径、累计左叶子。不管你是准备面试、考研复试还是单纯想把递归练扎实把这四道题吃透后面再遇到二叉树的题目心里会踏实非常多。我不打算把题解念一遍而是按照实际刷题的顺序把每一步的思考过程、写法差异、还有那些“正常人写不出来一测就崩”的细节都摊开讲。内容里会穿插明显的踩坑记录和调试经验希望能帮你少走点弯路。1. 拿到二叉树题目先想三步这四道题到底在考什么很多人刷二叉树最大的问题不是不会写代码而是拿到题之后不知道从哪里下手脑子里没有一个固定的分析框架。我自己的习惯是任何一道二叉树题目到手先按三步走确定递归函数的返回值和参数、确定终止条件、确定单层递归逻辑。这三步俗称“递归三部曲”几乎是所有二叉树递归题的通用解法骨架。1.1 递归三部曲就是二叉树的“解题脚手架”第一步明确这个递归函数“返回什么、需要什么参数”。第二步想清楚什么时候递归可以停也就是节点为空时返回什么值。第三步也是最关键的只考虑“当前节点、左孩子、右孩子”这一层的关系把所有复杂逻辑压缩到这一层里剩下的事情交给递归。打个比方递归就像一队人传话第一个人只需要知道“我该把话传给左边还是右边”不需要知道队伍最后一个人怎么回答。每一层都只负责处理自己这一层的逻辑然后信任下一层的返回值。这个思维方式一旦建立起来二叉树的题会突然变得非常简单。1.2 为什么说这四道题是一套组合拳这四道题并非随意拼凑它们在难度和思路上是递进的。222 完全二叉树的节点个数考的是“后序遍历 合并结果”最基础的递归计数模型110 平衡二叉树考的是“高度计算 状态传递”开始引入哨兵值和剪枝思想257 二叉树的所有路径考的是“前序遍历 回溯”这是深度优先搜索里最经典的路径收集模型404 左叶子之和考的是“遍历 条件过滤”在遍历过程中根据特定条件筛选节点。把它们放在同一天刷你会发现同一个套路被反复使用递归进出、返回值拼接、回溯撤销。把这几道题从暴力解法一路优化到最优解整个二叉树递归的体系就通了。1.3 前置基础遍历顺序不知道后面全是坑二叉树的前序、中序、后序、层序遍历一定要了如指掌。简单说前序是“先处理当前节点再递归左子树和右子树”中序是“先递归左子树处理当前节点再递归右子树”后序是“先递归左子树和右子树最后处理当前节点”。层序则是借助队列按层扫描这个在“求深度”“求层数”时非常好用但在“收集路径”这类与遍历方向强相关的场景里不如深度优先遍历自然。一个简单的判断口诀如果当前这一层逻辑依赖左右子树的计算结果用后序如果当前这一层逻辑需要先处理当前节点再往下探索用前序。后面讲的四道题会反复验证这两句话。2. 222 完全二叉树的节点个数暴力解法五分钟最优解藏着一个数学规律222 这道题在 LeetCode 上是中等难度但说实话普通解法并不难。难的是题目名字里带“完全二叉树”四个字暗示你要利用这个结构的特性去做优化。很多人直接按普通二叉树写了递归也能过但没拿到这题真正的精髓。我的建议是先把暴力解法写出来再理解优化解法最后把优化解法吃透。2.1 完全二叉树和满二叉树的区别先搞清楚完全二叉树指的是除了最后一层外每一层都是满的并且最后一层的节点都靠左排列中间不能有空档。也就是说最后一层如果有没填满的地方只能是右侧空缺左侧必须连续有节点。满二叉树则是每一层都填满总节点数恰好等于 2^h - 1其中 h 是高度。满二叉树一定是完全二叉树完全二叉树不一定是满二叉树。这个区别直接关系到优化解法的核心逻辑如果一棵子树是满二叉树那么它的节点个数可以直接用公式算出来不需要递归遍历每一个节点。2.2 解法一普通二叉树的递归计数O(N) 复杂度最简单的写法是后序遍历def countNodes(root): if not root: return 0 left_count countNodes(root.left) right_count countNodes(root.right) return left_count right_count 1这段代码的思路就是“先数左子树有多少节点再数右子树有多少节点最后加上自己”。每个节点都会访问一次时间复杂度 O(N)空间复杂度 O(log N) 到 O(N) 取决于树是否平衡。这种写法在完全二叉树和普通二叉树上都一样没有任何额外利用结构特性所以是“保底解法”。注意这里用后序遍历是因为当前节点的计数必须依赖左右子树的计数结果这正好呼应前面说的规律。你在纸上画一棵三层满二叉树把递归调用顺序展开会发现它本质上就是一次后序遍历。2.3 解法二利用完全二叉树性质把时间复杂度降到 O(logN × logN)优化解法的思路很巧妙从根节点开始每次都判断以当前节点为根的子树是不是满二叉树。判断方法也简单从当前节点出发一路往左走记录深度 leftDepth一路往右走记录深度 rightDepth。如果 leftDepth 等于 rightDepth说明这棵子树是满二叉树那么节点数直接用 2^leftDepth - 1 返回如果不相等就递归计算左右子树的节点数再加上当前节点本身。def countNodes(root): if not root: return 0 left_depth 0 right_depth 0 p root.left while p: left_depth 1 p p.left p root.right while p: right_depth 1 p p.right if left_depth right_depth: return (1 left_depth) - 1 return countNodes(root.left) countNodes(root.right) 1这个解法最妙的地方是你不需要走进每个节点只需要沿着左右边界往下走判断满二叉子树就直接用公式算出来不是满二叉树再继续递归。由于完全二叉树的特性每递归一层至少有一棵子树是满的所以总的计算量被大幅压缩。时间复杂度是 O(logN × logN)这里的证明我建议你背下来因为完全二叉树的高度是 O(logN)每一层判断左右深度需要遍历边界节点 O(logN)相乘就是 O(log²N)。# 位运算的坑注意别写错 return (1 left_depth) - 12.4 深度从 0 还是从 1 开始算一个不注意就错一位很多人在实现时的迷惑点是深度的初始值。我上面的代码里left_depth 和 right_depth 都是从 0 开始的因为根节点这一层没有算进去。比如一个满二叉树根节点左右都为空left_depth 和 right_depth 都是 0返回 (1 0) - 1 0这显然不对。等一下如果 root 不为空但左右孩子都为空那么这棵子树有且仅有根节点自己节点数是 1。上面的代码中 left_depth 和 right_depth 确实都等于 0返回 0 是错的对不对这里要特别注意代码里 while 循环是在排除了 null 之后沿边界走的。如果 root.left 不为空left_depth 会从 0 增加到 1如果 root.left 为空left_depth 保持 0。如果左右孩子都为空说明这棵树只有一个节点left_depth right_depth 0但返回公式应该是 1。所以正确的写法是当左右深度相等时节点数等于 2^(left_depth 1) - 1也就是 (1 (left_depth 1)) - 1。原因在于如果树的高度定义为从根到叶子的边数那么满二叉树的节点数是 2^(高度1) - 1如果树的高度定义为层数那节点数就是 2^层数 - 1。我之前第一次实现的时候就栽在这里后来把深度定义改成“从根节点开始往下数根节点自己的深度记为 1”问题就清晰了。建议你写的时候统一用“从当前节点出发能走到的最深层数”来理解判断满二叉树时左右深度相等意味着每一层都是满的节点数等于 2^层数 - 1层数用 left_depth 1 表示。这样避免出错。针对于上面的代码正确的满二叉树返回应该是(1 (left_depth 1)) - 1。这一点非常容易错强烈建议你推理一遍再跑测试。3. 110 平衡二叉树从“自顶向下重复计算”到“自底向上一次遍历”110 这题问的是一棵二叉树是不是高度平衡的定义是每个节点的左右子树高度差不超过 1。“每个节点”这四个字是题眼说明不能只检查根节点必须检查树里的每一个节点。3.1 高度和深度一字之差就是另一种题先把这个基础概念掰扯清楚深度是从根节点到当前节点经过的边数高度是从当前节点到最远叶子节点的最长路径边数。如果你是自上而下计算深度那是从根往叶子走如果你要计算高度则是从叶子往根的方向推。平衡二叉树判断里用的是“高度”因为我们要判断一个节点的子树整体有多高涉及的是从该节点到最远叶子的距离。重灾区预警网上很多错误写法是“计算每个节点左右子树深度差”本质上也是在算高度但代码里用 int leafDepth() 这种递归函数很容易在参数传递时搞混。我建议直接用“后序遍历求高度”的思路不要纠结深度概念。3.2 自顶向下的写法能过但效率不高最容易想到的写法是写一个高度函数然后在主函数里判断当前节点左右子树高度差再递归检查左右子树是否平衡。def isBalanced(root): if not root: return True left_height height(root.left) right_height height(root.right) if abs(left_height - right_height) 1: return False return isBalanced(root.left) and isBalanced(root.right)这个写法逻辑上没错坏就坏在高度函数在每个节点都被重复调用。根节点计算一次整棵树的高度左孩子又计算一次左子树的高度右孩子再算一次右子树的高度一层层往下大量高度被重复计算时间复杂度最坏能达到 O(N²)。如果面试官问“能不能优化”你就要想到自底向上的解法。3.3 自底向上的核心用一个叶子返回值同时传递“高度”和“是否平衡”我在实际刷题中最喜欢用的技巧是递归函数返回当前子树的高度如果当前子树已经不平衡了就返回一个特殊值 -1 作为“失败标记”。由于正常树的高度永远不会是负数所以 -1 这个哨兵值是安全且唯一的。def isBalanced(root): def height(node): if not node: return 0 left_h height(node.left) if left_h -1: return -1 right_h height(node.right) if right_h -1: return -1 if abs(left_h - right_h) 1: return -1 return max(left_h, right_h) 1 return height(root) ! -1这段代码的精妙之处在于只要某棵子树不平衡-1 会被一路向上传父节点看到左子树返回 -1 或者右子树返回 -1就直接返回 -1不再展开计算相当于剪枝。每个节点只被访问一次时间复杂度 O(N)空间复杂度 O(H)H 是树的高度也就是递归栈深度。3.4 为什么 -1 哨兵值比全局 flag 优雅有些同学会写一个全局变量一发现不平衡就置为 False后面递归继续跑最后判断这个变量。这样也能过但有两个问题一是全局变量在并发或多次调用时容易留下脏状态二是明明已经知道不平衡还要继续递归浪费性能。用 -1 哨兵值的好处是状态通过返回值传递递归天然具备“提前回溯”的能力代码也更简洁。这算是我强烈推荐的一种写法。4. 257 二叉树的所有路径前序遍历加回溯一个 string 参数让你少写一半代码257 这题要求从根节点到所有叶子节点的路径题目本身就规定了输出格式是字符串列表比如 1-2-5。这题是回溯思想的入门经典也是二叉树题目里最容易“看起来会写、一提交就错”的一道。4.1 为什么路径收集必须用前序遍历不能用后序路径的定义是“从根节点到叶子节点”这意味着你必须从根出发沿着一条路径往叶子方向走过程中记录走过的节点。这天然匹配前序遍历的顺序先处理当前节点再递归左右子树。而后序遍历是先处理子节点再回到父节点此时已经错过了沿路径记录的时机所以不合适。在遍历过程中每走一步就记录当前节点当走到叶子节点时把整条路径输出。要探索另一条路径时需要把之前加入的节点回退掉这就是“回溯”。你可以把回溯想象成走迷宫走到一个死胡同发现不是叶子就得退回上一个岔路口把刚才在路径上做的标记擦掉。4.2 标准写法path 数组加显式回溯我在 LeetCode 上最常用的写法是def binaryTreePaths(root): 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注意看这行path.pop()它写在递归调用结束之后不管当前节点有没有左右孩子都执行。因为 path 是可变的列表函数间共享同一个引用所以在返回上一层之前必须手动撤销刚才的添加操作否则路径会越攒越长出现 1-2-3- 这种错误结果。4.3 隐式回溯把路径参数改成字符串代码更简短另一个非常常见的写法是递归参数中路径不传引用而是每次都拼接一个新的字符串传进去。这样不需要显式 pop因为每层递归拿到的是新字符串返回上一层时原来的字符串并不受影响。def binaryTreePaths(root): res [] if not root: return 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(new_path) else: dfs(node.left, new_path -) dfs(node.right, new_path -) dfs(root, ) return res这种写法更短更直观很多初学者反而更喜欢。代价是每一层递归都会创建新的字符串如果树的节点数很多字符串拼接的开销会明显变大时间复杂度带上了路径长度的线性因子。一般来说面试时不会卡这个常数但如果你追求性能用列表加显式回溯的写法更优。4.4 终止条件的位置决定了你会不会多打印出错误路径这题最关键的细节是递归的终止条件应该判断“当前节点是叶子”而不是“当前节点为空”。有些同学写if not node: res.append(path) return这样会导致非叶子节点的路径也被输出或者把同一路径重复输出多遍。正确做法是走到空节点就直接 return不做任何输出但一旦发现当前节点既没有左孩子也没有右孩子就说明是叶子节点此时输出整条路径并 return。为什么不能把叶子判断放在空节点之前因为如果一棵子树为空走到空节点时你根本不知道它是来自左还是右路径本身已经包含了路径信息直接返回即可不需要额外判断。5. 404 左叶子之和你以为在遍历叶子其实考的是“父节点的视角”404 这题名字听起来很好懂求所有“左叶子节点”的数值之和。但实际一写很多人立刻卡住因为“左叶子”这个定义里包含了两个条件首先得是叶子节点其次得是某个父节点的左孩子。这两个条件放在一起意味着你不能站在这个节点本身来判断必须站在它的父节点往下看。5.1 左叶子的定义与边界条件叶子节点的定义是既没有左孩子也没有右孩子的节点。那么左叶子就是它是父节点的左孩子同时它自己没有孩子。拿一棵最简单的树举例根节点有左孩子左孩子是叶子那么这个左孩子的值就应该被计入总和。有个常见的坑根节点只有一个左孩子且这个左孩子是叶子这个左孩子是不是左叶子答案是“是”因为“左”是相对它的父节点根节点来说的。反过来如果根节点没有父节点那么根节点本身永远不可能是任何人的左叶子因为没人把它当作左孩子。另一个坑是如果一个节点有左孩子但这个左孩子有右子树那么这个左孩子不是叶子不能计入总和。判断的时候一定要先检查“左右都为空”这个叶子条件再判断“是左边”这个位置条件。5.2 站在父节点看问题每层只处理“当前节点的左孩子”我的实现思路是这样的递归遍历所有节点在每个节点上不需要判断自己是不是左叶子而是判断“我的左孩子是不是左叶子”。如果是就累加左孩子的值然后继续递归处理左子树和右子树。def sumOfLeftLeaves(root): 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 sumOfLeftLeaves(root.left) total sumOfLeftLeaves(root.right) return total这个代码读起来很顺先处理当前节点能不能贡献左叶子的值然后递归左右子树把左右子树的左叶子和加起来。如果 root.left 本身就是叶子递归进去后 sumOfLeftLeaves(root.left) 会发现 root.left 为空返回 0不会重复计算这个递归的逻辑是自洽的。5.3 为什么很多人会写成“在叶子节点上判断方向”然后卡死有些同学会先判断当前节点是不是叶子如果是叶子再想办法往上找父节点判断是不是左孩子。但二叉树递归里“往上找父节点”是很别扭的除非你给递归函数额外传一个布尔参数比如isLeft。这种写法也能实现但会引入额外的状态变量容易出错。def dfs(node, is_left): if not node: return 0 if not node.left and not node.right and is_left: return node.val return dfs(node.left, True) dfs(node.right, False)这个写法其实也不难看但我个人更喜欢“父节点视角”的写法因为代码不需要维护 is_left 这个状态直接利用递归结构本身。两种都能过看你自己习惯哪种。5.4 递归顺序的差异不影响结果但影响理解有的题解会把这题写成后序遍历def sumOfLeftLeaves(root): if not root: return 0 left_sum sumOfLeftLeaves(root.left) right_sum sumOfLeftLeaves(root.right) if root.left and not root.left.left and not root.left.right: left_sum root.left.val return left_sum right_sum这种写法把“累加左叶子”这件事放在处理完左右子树之后逻辑上是一棵后序遍历树。我个人觉得前序版本更符合直觉因为你每走到一个节点第一时间判断它的左孩子是不是左叶子然后才递归深入。无论前序还是后序只要保证能访问到每个节点的左孩子并且判断叶子条件结果都是正确的。6. 实操复盘为什么你的二叉树程序总报运行时错误标题里的热搜词有一条是“写二叉树程序时为什么总是报运行时错误”这几乎是刷二叉树题目时最容易遇到的一类问题了。我在这里把自己调试这类问题的完整思路整理成一套流程后面你遇到问题可以直接按这个顺序排查。6.1 运行时错误的两个最大元凶空指针和栈溢出二叉树题目的运行时错误十有八九是在访问空节点的属性比如写了root.left.val但 root 本身是 None或者node.left是 None你却尝试访问node.left.val。这类错误的经典触发场景就是递归边界处理不严谨。另一个常见的运行时错误是递归栈溢出。当树特别深比如链表化的二叉树有 10 万层递归函数无法在栈空间内跑完程序直接抛出栈溢出。这种情况要从终止条件入手检查看递归是否真的能收敛或者考虑改用迭代写法避免栈深度限制。6.2 一个真实的报错调试案例257 的路径重复输出我刷 257 的时候第一版代码长这样def binaryTreePaths(root): 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)) dfs(node.left, path) dfs(node.right, path) dfs(root, []) return res看起来好像没问题但运行测试用例时像这样的树1 - 2 - 3每个节点只有左孩子输出竟然是[1-2-3, 1-2-3]路径被输出了两遍。我调试了很久才发现问题出在递归到叶子节点 3 时发现 left 和 right 都为空输出路径但是代码随后还继续执行了dfs(node.left, path)和dfs(node.right, path)也就是向两个 None 节点各递归了一次。虽然对结果没影响但接下来的调用各自都带着 path 重新走了一遍然后因为提前 return 而没有 pop把 path 搞乱了。正确的做法是在输出完叶子路径后直接 return不再往下递归。我在 4.2 的代码里加了else分支把非叶子节点才继续递归。这个区别看着微小却是很多 bug 的来源。6.3 一套必测的测试用例清单建议收藏我每次写完二叉树题都会跑一遍这组测试用例能帮你快速暴露大部分边界问题测试输入预期结果主要考察点[]空树返回空结果空节点处理[1]单节点节点数 1路径 [1]左叶子和 0叶子边界判断[1,2,3]一般的三节点树路径含 1-2 和 1-3左右孩子路径收集[1,null,2,3]只有右子树的树路径 1-2-3空左子树的跳过[1,2,2,3,3,null,null,4,4]不平衡斜坡树平衡判断 False左右子树高度差链表形二叉树每个节点只有右孩子深度较大递归栈性能有了这份清单你可以快速定位自己的题解到底哪里写得不对。我在刷完全二叉树的节点个数时就是靠单节点和空树这两个用例发现了 2.4 节的深度计算错误。6.4 用调试打印法观察递归路径我不太建议初学者一上来就只会用断点调试器。遇到二叉树递归题我建议先在递归函数入口处打一行 print把当前节点、当前路径状态都打出来然后观察输出。比如在 257 的 dfs 里加上print(fvisiting {node.val}, path{path})你很快就会看到递归的“深入”和“回溯”过程很多逻辑错误一目了然。等到调试完毕记得把 print 删掉再提交不然会拖慢运行时间有些在线评测还会因为你输出调试信息而误判结果。7. 延伸思考从这四道题看二叉树的更多变体刷完这四道题你会发现自己的递归能力有了质的提升。但如果就此打住还是有点可惜。顺着这四道题的主线可以再往几个方向延伸。7.1 把 222 的思路迁移到搜索二叉树的节点统计搜索二叉树BST有一个重要性质左子树的所有节点值都小于根右子树的所有节点值都大于根。如果你要统计 BST 的节点个数可以沿用后序遍历的计数模型但还能利用有序性做更多操作比如“统计区间 [low, high] 内的节点个数”。这种题本质上是把遍历和条件判断结合在一起递归框架跟 222 如出一辙。7.2 平衡判断在 AVL 树和红黑树里的地位110 的平衡判断本质上是 AVL 树维护平衡因子的底层逻辑。AVL 树在插入、删除节点后就是通过检查左右子树高度差来确认是否失衡失衡时通过旋转操作恢复平衡。你理解了 110 的自底向上高度计算再看 AVL 的旋转就会明白为什么平衡因子是 -1、0、1 这样的取值。7.3 线索二叉树为什么路径收集和遍历顺序有关系“线索二叉树”这个热词也顺便说一下。线索二叉树的出现是为了解决二叉树遍历时递归栈过深、浪费空间的问题。它利用原本为空的指针指向遍历序列中的前驱和后继节点。理解了 257 的路径收集为什么要用前序你会更深刻体会“遍历顺序”在二叉树操作里的分量不同顺序决定了节点的处理时机也就决定了你能在遍历过程中做什么样的记录。回到这四道题本身我个人在实际刷题中最大的体会是二叉树递归的难点不在“递归”本身而在“你在递归的过程中对状态的把握”。数节点时你要合并返回值判平衡时你要传递哨兵值收路径时你要回溯撤销算左叶子时你要从父节点视角判断。这四种状态操作恰好覆盖了递归函数设计的几乎所有关键手法。把这四道题写顺后面遇到更复杂的树形结构题目比如树的序列化、最近公共祖先、二叉树的最大宽度思路都会顺很多。最后再分享一个小技巧刷二叉树题目时如果脑子转不过弯就拿一支笔在纸上画一棵三层的树把递归过程一步一步展开画出来。大部分人对递归的恐惧都是因为没看过它实际执行的样子真看懂了后面会越写越顺手。