树的练习系列写到第4题编号1302题目全称是“层数最深的叶子节点的和”。我第一眼看到这题以为就是先求一个最大深度然后再遍历一遍树把符合条件的叶子值加起来。可真到动手写代码、提交、踩坑之后才发现边界条件、递归返回值的组织方式、全局变量的清理每一个点都能让人翻车。这篇文章会把这段刷题过程完整记录下来包括我尝试过的三种解法、为什么最后用BFS收尾、以及哪些坑是新手最容易踩的。如果你正在练二叉树相关题目或者准备面试想快速过一遍树的遍历题这篇可以当一份踩坑笔记来读。1. 题目核心拆解为什么这道题值得做1.1 题目到底在问什么题目给一棵二叉树的根节点 root要求返回“层数最深的叶子节点的和”。这里的“层数最深”可以理解为“整棵树的最大深度所在的那一层”。举个例子如果一棵树只有左子树一路向下右侧比较矮那么最深层只在左子树的某个叶子节点上答案就是那一个节点的值。这里有一个容易被忽略的等价关系在一棵非空二叉树中深度最大那一层上的节点一定都是叶子节点。因为如果某个节点还有孩子那么它所在层就不是最大深度层孩子所在的层更深。所以“层数最深的叶子节点”和“最后一层的所有节点”在结果上是同一个集合。想明白这一点之后解法思路就清晰了可以先求最大深度再按深度筛选也可以直接一层一层往下走走到最后一层的时候把这一层的节点值加起来。1.2 叶子节点的定义与边界情况叶子节点是没有左孩子且没有右孩子的节点。这里要特别注意根节点如果整棵树只有一个节点根节点既没有左孩子也没有右孩子那它自己就是叶子。root [1] 时答案应该是1。root []也就是空树答案应该是0。另一个容易踩的边界是节点值。题目的节点值范围往往包含0甚至负数。判断叶子节点只能用结构判断也就是not node.left and not node.right绝对不能写成if node.val and ...。这个错误我见过很多次尤其当叶子值是0时条件判断为 False整个节点就被漏掉。后文“常见问题”里我会再展开。还需注意最深层可能只有一个叶子也可能有很多个叶子。不要把它想象成满二叉树那样“最后一层应该是 2 的某次方个节点”。普通二叉树的最深层可以只有一个节点也可以左右子树同时存在多个深度相同的叶子。求和时有多少个就加多少个。2. 解法一先求最大深度再二次遍历2.1 深度优先求最大深度最直观的思路是分两步走。第一步求整棵树的最大深度第二步再次遍历这棵树找到所有深度等于最大深度的叶子节点并把它们的值累加。求最大深度可以用递归也可以写成迭代。递归版本最简洁def max_depth(root): if not root: return 0 return 1 max(max_depth(root.left), max_depth(root.right))这个递推关系可以理解成空树的深度是0非空树的深度等于左子树深度和右子树深度的最大值再加上当前节点本身的这一层。很多初学者一开始会疑惑为什么返回的是1 max(...)其实就是把根节点所在层数也计入了。如果约定根节点的深度为1那么整棵树的深度就是这个公式。2.2 收集目标叶子节点值求出最大深度 maxD 之后再写一个辅助 DFS 函数边遍历边判断def dfs(node, depth): if not node: return 0 if not node.left and not node.right and depth maxD: return node.val return dfs(node.left, depth 1) dfs(node.right, depth 1)这段代码的逻辑是当前节点是空节点时返回0当前节点是叶子且深度正好等于最大深度时返回这个叶子的值否则继续往左右子树递归把两侧结果加起来。如果某个叶子深度不是最大深度它的返回值就是0不会影响最终和。这种写法非常好理解几乎不需要解释。我第一次刷这题时用的就是它因为先把“求最大深度”和“按深度取叶子值”两个动作拆开思路非常顺。缺点是遍历了两次树第一次求深度第二次求和。虽然时间复杂度仍然是 O(n)但常数上比一次遍历要大。2.3 复杂度与适用场景时间复杂度O(2n) O(n)每个节点最多访问两次。空间复杂度O(h)h 是树高递归栈最大深度等于树高。适用场景刚接触二叉树的新手或者面试时时间紧张、想快速给出正确解法的情况。这种方案的最大优点是不会在递归返回值设计上犯错因为每一步都很直白。但遇到退化树比如所有节点只有左孩子树高等于节点数 n递归深度可能达到 n。在线判题系统一般不会给这种极端输入但本地调试时如果树的节点数很大可能会触发递归深度限制。这也是为什么我更推荐后面两种解法。3. 解法二一次DFS递归返回深度与和3.1 返回值的巧妙设计既然题目既要关注“最大深度”又要求“对应深度叶子值的和”我们完全可以在一次递归中同时返回这两个信息。递归函数的返回值设计成一个元组(depth, sum)其中 depth 表示当前子树的最大深度sum 表示这个最大深度上所有叶子节点的值之和。核心逻辑是空节点返回(0, 0)。叶子节点返回(1, node.val)。非叶子节点分别递归左右子树拿到(l_depth, l_sum)和(r_depth, r_sum)。比较左右深度如果左子树更深返回(l_depth 1, l_sum)。如果右子树更深返回(r_depth 1, r_sum)。如果左右一样深返回(l_depth 1, l_sum r_sum)。这个设计的巧妙之处在于当左右子树最大深度一样时说明当前这棵子树的最深层同时出现在两侧那么最深层叶子值应该把两侧都加起来当一侧更深时另一侧的那些叶子虽然也是叶子但它们不在最深一层所以直接丢弃。3.2 递归细节与返回逻辑Python 完整实现如下def dfs(node): if not node: return (0, 0) if not node.left and not node.right: return (1, node.val) l_depth, l_sum dfs(node.left) r_depth, r_sum dfs(node.right) if l_depth r_depth: return (l_depth 1, l_sum) elif l_depth r_depth: return (r_depth 1, r_sum) else: return (l_depth 1, l_sum r_sum) def deepest_leaves_sum(root): if not root: return 0 return dfs(root)[1]这段代码有一个非常关键的细节必须单独特判叶子节点。如果不加这个特判叶子节点会继续往下递归到空节点返回(0, 0)然后左右深度相等当前节点返回(1, 0)这个叶子的值就彻底丢了。我第一次写的时候就是漏了叶子特判结果所有测试用例的输出都是0。另一个细节是深度都要加1。左子树返回的l_depth是“左子树这棵子树的高度”回到当前节点时还要把当前节点这一层算进去所以返回l_depth 1。我见过有人在这里忘记加1最终最大深度算出来总是比真实值小1看起来好像不影响某些用例但一旦左右子树深度恰好只差1结果就会错得莫名其妙。3.3 状态转移过程拆解拿一棵具体的树来推演一遍1 / \ 2 3 / \ \ 4 5 6先看节点2这一层。节点2的左右孩子分别是4和5它们都是叶子节点。递归进入4返回(1, 4)进入5返回(1, 5)。左右深度都是1相等所以节点2返回(2, 459)。再看节点3这一层。节点3的右孩子是6左孩子为空。递归左空节点返回(0, 0)递归右叶子6返回(1, 6)。右深度1大于左深度0所以节点3返回(2, 6)。最后看根节点1。左边拿到(2, 9)右边拿到(2, 6)左右深度都是2相等所以根节点返回(3, 9615)。最终答案就是15对应最深层叶子4、5、6的值之和。再看一棵不平衡的树1 / 2 / 3节点2左孩子3返回(1, 3)右空节点返回(0, 0)左深度更大所以节点2返回(2, 3)。根节点左边返回(3, 3)右边空节点返回(0, 0)最终返回(4, 3)。答案是3也就是最底层那个单独叶子的值。从这个例子能看出当一侧更深时较浅那一侧的所有信息都会被丢弃这正是题目的要求。这种一次遍历返回多个状态的思路是树形 DP 的入门模板。后面做“二叉树直径”“二叉树最大路径和”“判断平衡二叉树”时都会用到类似的设计。所以这道题虽然简单却值得认真写一遍。4. 解法三BFS层序遍历最后一层收网4.1 层序遍历框架BFS 的思路更贴近题目的字面意思从根开始一层一层往下扫扫完一层再扫下一层等所有层都扫完最后一次记录的“当前层节点值和”就是最深层叶子节点的和。用队列实现层序遍历是标准动作from collections import deque def deepest_leaves_sum(root): if not root: return 0 q deque([root]) ans 0 while q: ans 0 for _ in range(len(q)): node q.popleft() ans node.val if node.left: q.append(node.left) if node.right: q.append(node.right) return ans这里的关键是每次进入 while 循环时把 ans 重新置为0。进入循环时队列里恰好是当前层的所有节点所以用一个 for 循环把这一层全部处理完。处理完当前层之后队列里装的是下一层的所有节点继续下一轮循环。当整个 while q 结束ans 就是最后一层节点的值之和。4.2 为什么最后一层就是最深叶子有人会问最后一层节点一定是叶子吗是的。原因很简单如果某个节点出现在最后一层但它还有左孩子或右孩子那么队列里一定会把它的孩子加入到下一轮中也就是说这层根本不会是最后一层。只有当某个节点没有任何孩子时它才会真正成为最后一个不为空的节点。所以 BFS 版本不需要再单独判断not node.left and not node.right。如果你额外加上这个判断也不会错但属于冗余操作。我在代码注释里会写一行“最后一层节点一定是叶子”这样其他人读代码时不会困惑为什么没有叶子判断。4.3 BFS相对DFS的优势DFS 的递归解法和树高有关在极端退化树比如每个节点只有一个右孩子上树高等于 n递归深度可能达到 n一旦 n 很大就容易爆栈。BFS 使用显式队列不依赖调用栈所以没有递归爆栈的风险。空间复杂度方面BFS 是 O(w)w 是树的最大层宽度。最坏情况下一棵完全二叉树的最后一层大约有 n/2 个节点所以空间复杂度是 O(n)。DFS 递归版本的空间复杂度是 O(h)在满二叉树中 h 约等于 log nDFS 更省空间但在退化树中 h nDFS 反而更危险。所以 BFS 和 DFS 并不是谁绝对更好而是取决于应用场景。在线判题的数据通常两种都能过但在生产环境或面试中如果题目明确说“树可能很大”或者“避免递归”BFS 是更稳的选择。5. 完整代码与测试用例验证5.1 可运行代码我最后在题库提交的版本是 BFS因为代码最不容易在返回值设计上出错而且队列层序遍历本身就是面试高频考点。完整可运行的代码如下from collections import deque from typing import Optional class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def deepestLeavesSum(self, root: Optional[TreeNode]) - int: if not root: return 0 q deque([root]) ans 0 while q: ans 0 for _ in range(len(q)): node q.popleft() ans node.val if node.left: q.append(node.left) if node.right: q.append(node.right) return ans如果你更想用一次递归版本可以把第 3 节的dfs放进类方法中。两种解法在判题系统上耗时都很低我用本地测试跑过几百个随机树结果完全一致。5.2 边界用例测试清单我在本地会固定跑下面几类用例确保代码不是“碰巧通过”用例结构期望结果空树root None0单节点root TreeNode(5)5单链1 - 2 - 3 - 44普通树[1,2,3,4,5,None,6]15叶子值为0root TreeNode(0)0左右同深[1,2,3,4,5,6,7]22其中“叶子值为0”的用例特别关键。如果你写的判断是if node.val and not node.left and not node.right单节点为0时会被漏判直接返回0但从题目语义来看正确答案也确实是0所以它会错误地“通过”。这就是为什么测试用例不能只看输出还要在代码逻辑层面保证判断依据是结构而不是值。5.3 三种解法复杂度对比解法时间复杂度空间复杂度代码复杂度适用场景两次遍历DFSO(n)O(h)低新手理解思路一次DFS返回元组O(n)O(h)中面试展示状态合并BFS层序O(n)O(w)低树高可能很大时这里的 h 是树高w 是最大层宽度。普通二叉树中 h 和 w 都可能达到 n所以理论最坏情况都是 O(n)。但实际刷题时追求的不只是复杂度还有“思路清楚、不容易写错”以及“赶紧写出能通过的代码”。BFS 版本对初学者最友好一次DFS版本最锻炼递归设计能力两次遍历版本最直白但代码最啰嗦。6. 常见问题与误区的深度排查6.1 全局变量残留问题我最早尝试的版本是递归加全局变量max_depth 0 total 0 def dfs(node, depth): global max_depth, total if not node: return if not node.left and not node.right: if depth max_depth: max_depth depth total node.val elif depth max_depth: total node.val return dfs(node.left, depth 1) dfs(node.right, depth 1)这个思路本身是对的但有个很大的隐患如果写成类方法中的self.max_depth和self.total多次调用同一个实例对象时上一次的结果会残留下来。判题系统通常会每次创建新对象所以不出问题但我在本地连续测试多个用例时发现第二次的答案会把第一次的值加进去越加越大。解决办法是在入口处重置self.max_depth 0 self.total 0或者在嵌套函数里用nonlocal声明并手动归零。这个坑属于典型的“本地测试和在线判题环境不一致”问题不亲身踩一次很难意识到。6.2 递归返回深度忘记加1一次DFS返回(depth, sum)的写法中最隐蔽的错误是返回时忘记加1。比如if l_depth r_depth: return (l_depth, l_sum)这样写返回的深度不包含当前节点这一层一路往上会把整棵树的深度算小。这种错误很麻烦因为它不会让你直接得到0或一个完全离谱的数而是可能在某个节点上比较左右子树深度时产生偏差导致最后把不是最深的叶子也算进去。我建议写完递归后手动用一棵三层满二叉树过一遍叶子返回1父节点返回2根节点返回3。如果根节点最终返回的不是3那一定就是某个地方把加1漏掉了。6.3 节点值等于0时被误判再强调一遍判断叶子只能用结构不能用值。下面这种写法是经典错误if node.val and not node.left and not node.right: ans node.val当叶子节点的值是0时node.val为 False整个 if 块不会执行。这种情况如果整棵树只有一个值为0的节点答案本来应该是0错误代码也返回0反而不容易暴露。但如果有多个叶子比如最深层叶子值是 [0, 3]正确结果应该是3错误代码会由于跳过0而返回3结果碰巧一致。再比如最深层有两个叶子值都是0正确结果是0错误代码也返回0。这导致很多测试用例都无法发现 bug属于“侥幸通过”的典型。所以必须在代码里养成只用not node.left and not node.right判断叶子的习惯。6.4 嵌套函数中的作用域问题在类方法里定义嵌套递归函数时如果希望修改外层局部变量需要声明nonlocal或者用可变容器包一层。比如class Solution: def deepestLeavesSum(self, root): ans 0 def dfs(node, depth): nonlocal ans if not node: return ...如果不写nonlocalPython 会认为ans是一个新的局部变量赋值时会报UnboundLocalError。另一种常见做法是用self.ans这样不受作用域限制但要记得在入口处重置。面试白板编程时这个细节经常被忽略建议提前想好自己习惯用哪种方式。还有一种写法是把 ans 放在长度为1的列表里ans [0] def dfs(...): ans[0] node.val这样也能绕过作用域限制但代码可读性差一些我一般不推荐。7. 本地调试技巧与扩展思考7.1 手动构造二叉树的辅助函数刷题时最痛苦的事情之一是在本地手动构造测试树。我写了一个简单的辅助函数按层序列表构造二叉树方便把题目示例直接转成树对象from collections import deque def build_tree(nodes): if not nodes: return None root TreeNode(nodes[0]) q deque([root]) idx 1 while idx len(nodes): node q.popleft() if nodes[idx] is not None: node.left TreeNode(nodes[idx]) q.append(node.left) idx 1 if idx len(nodes) and nodes[idx] is not None: node.right TreeNode(nodes[idx]) q.append(node.right) idx 1 return root这个函数的逻辑很简单用队列按层扫描每次从队列里取出一个节点然后从列表里取两个元素作为它的左右孩子。列表里的None表示没有孩子。有了这个函数我就可以把题目示例写成root build_tree([1, 2, 3, 4, 5, None, 6]) print(Solution().deepestLeavesSum(root))输出就是15。本地验证速度比直接在浏览器里提交快得多。7.2 打印遍历过程辅助理解如果递归写得很晕我会在递归函数里加打印观察每个节点返回了什么。比如def dfs(node): if not node: return (0, 0) if not node.left and not node.right: return (1, node.val) l_depth, l_sum dfs(node.left) r_depth, r_sum dfs(node.right) print(node.val, l_depth, l_sum, r_depth, r_sum) ...打印出来的每一行能清楚看到左右子树的返回结果。这个方法尤其适合调试“返回深度忘记加1”这类问题。等你把思路理清楚后再把打印去掉。7.3 从这道题出发的变体1302 题本身不难但可以做很多变体练习最深层所有节点的平均值BFS 最后一层累加后除以该层节点个数。最深层叶子节点的个数BFS 最后一层每加一个值就计数。最深层最左侧叶子节点的值BFS 时记录最后一层第一个出队节点。最深层节点中值最大的节点BFS 最后一层用一个变量维护最大值。这些变体的核心逻辑都和原题一致只是最后一层处理方式不同。练完 1302 后可以把“二叉树的层平均值”“二叉树最大深度”“二叉树最小深度”一起刷一遍你会发现层序遍历的框架一脉相承。8. 一点刷题心得8.1 这道题教会我的三件事第一读题要到“等价关系”的层面。“层数最深的叶子节点”和“最后一层节点”是同一个集合这个等价关系直接指向 BFS 解法。很多题目的难点不是代码而是对题面描述的翻译。第二递归返回值可以是一个“状态包”。只返回一个值有时候解决不了问题返回(depth, sum)就能在一次遍历内同时拿到两个信息。这种设计思路比“先全局变量再清零”要优雅得多也更可靠。第三边界条件必须靠“结构判断”不能靠“值判断”。叶子节点用not node.left and not node.right判断不要用node.val判断。节点值是0时后者会让你的代码在最需要正确的时候出错。8.2 给同样在练树的人的建议树的题目特别适合“一题多解”。我强烈建议你拿到题之后不要只满足于一种解法通过而是把两步遍历、一次递归、BFS 三种方法都写一遍。这样练习一次相当于把二叉树的基本功重新梳理了一遍。写的过程中遇到问题也不要立刻看题解先用打印或者构造特殊用例的方式自己排查排查的过程就是长经验的过程。我个人在实际操作中的体会是算法题刷到最后拼的不只是灵感和记忆而是对基础数据结构的熟练度。像 1302 这种看似简单的题反而最能检验你对深度、层数、叶子节点这些基础概念是否真的理解得透。把它彻底吃透后面遇到更复杂的树形 DP 题目你会觉得从容很多。希望这篇记录能帮正在练树专题的你少走几步弯路。 LeetCode 1302 二叉树最深叶子节点和：递归与BFS全解析
树的练习系列写到第4题编号1302题目全称是“层数最深的叶子节点的和”。我第一眼看到这题以为就是先求一个最大深度然后再遍历一遍树把符合条件的叶子值加起来。可真到动手写代码、提交、踩坑之后才发现边界条件、递归返回值的组织方式、全局变量的清理每一个点都能让人翻车。这篇文章会把这段刷题过程完整记录下来包括我尝试过的三种解法、为什么最后用BFS收尾、以及哪些坑是新手最容易踩的。如果你正在练二叉树相关题目或者准备面试想快速过一遍树的遍历题这篇可以当一份踩坑笔记来读。1. 题目核心拆解为什么这道题值得做1.1 题目到底在问什么题目给一棵二叉树的根节点 root要求返回“层数最深的叶子节点的和”。这里的“层数最深”可以理解为“整棵树的最大深度所在的那一层”。举个例子如果一棵树只有左子树一路向下右侧比较矮那么最深层只在左子树的某个叶子节点上答案就是那一个节点的值。这里有一个容易被忽略的等价关系在一棵非空二叉树中深度最大那一层上的节点一定都是叶子节点。因为如果某个节点还有孩子那么它所在层就不是最大深度层孩子所在的层更深。所以“层数最深的叶子节点”和“最后一层的所有节点”在结果上是同一个集合。想明白这一点之后解法思路就清晰了可以先求最大深度再按深度筛选也可以直接一层一层往下走走到最后一层的时候把这一层的节点值加起来。1.2 叶子节点的定义与边界情况叶子节点是没有左孩子且没有右孩子的节点。这里要特别注意根节点如果整棵树只有一个节点根节点既没有左孩子也没有右孩子那它自己就是叶子。root [1] 时答案应该是1。root []也就是空树答案应该是0。另一个容易踩的边界是节点值。题目的节点值范围往往包含0甚至负数。判断叶子节点只能用结构判断也就是not node.left and not node.right绝对不能写成if node.val and ...。这个错误我见过很多次尤其当叶子值是0时条件判断为 False整个节点就被漏掉。后文“常见问题”里我会再展开。还需注意最深层可能只有一个叶子也可能有很多个叶子。不要把它想象成满二叉树那样“最后一层应该是 2 的某次方个节点”。普通二叉树的最深层可以只有一个节点也可以左右子树同时存在多个深度相同的叶子。求和时有多少个就加多少个。2. 解法一先求最大深度再二次遍历2.1 深度优先求最大深度最直观的思路是分两步走。第一步求整棵树的最大深度第二步再次遍历这棵树找到所有深度等于最大深度的叶子节点并把它们的值累加。求最大深度可以用递归也可以写成迭代。递归版本最简洁def max_depth(root): if not root: return 0 return 1 max(max_depth(root.left), max_depth(root.right))这个递推关系可以理解成空树的深度是0非空树的深度等于左子树深度和右子树深度的最大值再加上当前节点本身的这一层。很多初学者一开始会疑惑为什么返回的是1 max(...)其实就是把根节点所在层数也计入了。如果约定根节点的深度为1那么整棵树的深度就是这个公式。2.2 收集目标叶子节点值求出最大深度 maxD 之后再写一个辅助 DFS 函数边遍历边判断def dfs(node, depth): if not node: return 0 if not node.left and not node.right and depth maxD: return node.val return dfs(node.left, depth 1) dfs(node.right, depth 1)这段代码的逻辑是当前节点是空节点时返回0当前节点是叶子且深度正好等于最大深度时返回这个叶子的值否则继续往左右子树递归把两侧结果加起来。如果某个叶子深度不是最大深度它的返回值就是0不会影响最终和。这种写法非常好理解几乎不需要解释。我第一次刷这题时用的就是它因为先把“求最大深度”和“按深度取叶子值”两个动作拆开思路非常顺。缺点是遍历了两次树第一次求深度第二次求和。虽然时间复杂度仍然是 O(n)但常数上比一次遍历要大。2.3 复杂度与适用场景时间复杂度O(2n) O(n)每个节点最多访问两次。空间复杂度O(h)h 是树高递归栈最大深度等于树高。适用场景刚接触二叉树的新手或者面试时时间紧张、想快速给出正确解法的情况。这种方案的最大优点是不会在递归返回值设计上犯错因为每一步都很直白。但遇到退化树比如所有节点只有左孩子树高等于节点数 n递归深度可能达到 n。在线判题系统一般不会给这种极端输入但本地调试时如果树的节点数很大可能会触发递归深度限制。这也是为什么我更推荐后面两种解法。3. 解法二一次DFS递归返回深度与和3.1 返回值的巧妙设计既然题目既要关注“最大深度”又要求“对应深度叶子值的和”我们完全可以在一次递归中同时返回这两个信息。递归函数的返回值设计成一个元组(depth, sum)其中 depth 表示当前子树的最大深度sum 表示这个最大深度上所有叶子节点的值之和。核心逻辑是空节点返回(0, 0)。叶子节点返回(1, node.val)。非叶子节点分别递归左右子树拿到(l_depth, l_sum)和(r_depth, r_sum)。比较左右深度如果左子树更深返回(l_depth 1, l_sum)。如果右子树更深返回(r_depth 1, r_sum)。如果左右一样深返回(l_depth 1, l_sum r_sum)。这个设计的巧妙之处在于当左右子树最大深度一样时说明当前这棵子树的最深层同时出现在两侧那么最深层叶子值应该把两侧都加起来当一侧更深时另一侧的那些叶子虽然也是叶子但它们不在最深一层所以直接丢弃。3.2 递归细节与返回逻辑Python 完整实现如下def dfs(node): if not node: return (0, 0) if not node.left and not node.right: return (1, node.val) l_depth, l_sum dfs(node.left) r_depth, r_sum dfs(node.right) if l_depth r_depth: return (l_depth 1, l_sum) elif l_depth r_depth: return (r_depth 1, r_sum) else: return (l_depth 1, l_sum r_sum) def deepest_leaves_sum(root): if not root: return 0 return dfs(root)[1]这段代码有一个非常关键的细节必须单独特判叶子节点。如果不加这个特判叶子节点会继续往下递归到空节点返回(0, 0)然后左右深度相等当前节点返回(1, 0)这个叶子的值就彻底丢了。我第一次写的时候就是漏了叶子特判结果所有测试用例的输出都是0。另一个细节是深度都要加1。左子树返回的l_depth是“左子树这棵子树的高度”回到当前节点时还要把当前节点这一层算进去所以返回l_depth 1。我见过有人在这里忘记加1最终最大深度算出来总是比真实值小1看起来好像不影响某些用例但一旦左右子树深度恰好只差1结果就会错得莫名其妙。3.3 状态转移过程拆解拿一棵具体的树来推演一遍1 / \ 2 3 / \ \ 4 5 6先看节点2这一层。节点2的左右孩子分别是4和5它们都是叶子节点。递归进入4返回(1, 4)进入5返回(1, 5)。左右深度都是1相等所以节点2返回(2, 459)。再看节点3这一层。节点3的右孩子是6左孩子为空。递归左空节点返回(0, 0)递归右叶子6返回(1, 6)。右深度1大于左深度0所以节点3返回(2, 6)。最后看根节点1。左边拿到(2, 9)右边拿到(2, 6)左右深度都是2相等所以根节点返回(3, 9615)。最终答案就是15对应最深层叶子4、5、6的值之和。再看一棵不平衡的树1 / 2 / 3节点2左孩子3返回(1, 3)右空节点返回(0, 0)左深度更大所以节点2返回(2, 3)。根节点左边返回(3, 3)右边空节点返回(0, 0)最终返回(4, 3)。答案是3也就是最底层那个单独叶子的值。从这个例子能看出当一侧更深时较浅那一侧的所有信息都会被丢弃这正是题目的要求。这种一次遍历返回多个状态的思路是树形 DP 的入门模板。后面做“二叉树直径”“二叉树最大路径和”“判断平衡二叉树”时都会用到类似的设计。所以这道题虽然简单却值得认真写一遍。4. 解法三BFS层序遍历最后一层收网4.1 层序遍历框架BFS 的思路更贴近题目的字面意思从根开始一层一层往下扫扫完一层再扫下一层等所有层都扫完最后一次记录的“当前层节点值和”就是最深层叶子节点的和。用队列实现层序遍历是标准动作from collections import deque def deepest_leaves_sum(root): if not root: return 0 q deque([root]) ans 0 while q: ans 0 for _ in range(len(q)): node q.popleft() ans node.val if node.left: q.append(node.left) if node.right: q.append(node.right) return ans这里的关键是每次进入 while 循环时把 ans 重新置为0。进入循环时队列里恰好是当前层的所有节点所以用一个 for 循环把这一层全部处理完。处理完当前层之后队列里装的是下一层的所有节点继续下一轮循环。当整个 while q 结束ans 就是最后一层节点的值之和。4.2 为什么最后一层就是最深叶子有人会问最后一层节点一定是叶子吗是的。原因很简单如果某个节点出现在最后一层但它还有左孩子或右孩子那么队列里一定会把它的孩子加入到下一轮中也就是说这层根本不会是最后一层。只有当某个节点没有任何孩子时它才会真正成为最后一个不为空的节点。所以 BFS 版本不需要再单独判断not node.left and not node.right。如果你额外加上这个判断也不会错但属于冗余操作。我在代码注释里会写一行“最后一层节点一定是叶子”这样其他人读代码时不会困惑为什么没有叶子判断。4.3 BFS相对DFS的优势DFS 的递归解法和树高有关在极端退化树比如每个节点只有一个右孩子上树高等于 n递归深度可能达到 n一旦 n 很大就容易爆栈。BFS 使用显式队列不依赖调用栈所以没有递归爆栈的风险。空间复杂度方面BFS 是 O(w)w 是树的最大层宽度。最坏情况下一棵完全二叉树的最后一层大约有 n/2 个节点所以空间复杂度是 O(n)。DFS 递归版本的空间复杂度是 O(h)在满二叉树中 h 约等于 log nDFS 更省空间但在退化树中 h nDFS 反而更危险。所以 BFS 和 DFS 并不是谁绝对更好而是取决于应用场景。在线判题的数据通常两种都能过但在生产环境或面试中如果题目明确说“树可能很大”或者“避免递归”BFS 是更稳的选择。5. 完整代码与测试用例验证5.1 可运行代码我最后在题库提交的版本是 BFS因为代码最不容易在返回值设计上出错而且队列层序遍历本身就是面试高频考点。完整可运行的代码如下from collections import deque from typing import Optional class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def deepestLeavesSum(self, root: Optional[TreeNode]) - int: if not root: return 0 q deque([root]) ans 0 while q: ans 0 for _ in range(len(q)): node q.popleft() ans node.val if node.left: q.append(node.left) if node.right: q.append(node.right) return ans如果你更想用一次递归版本可以把第 3 节的dfs放进类方法中。两种解法在判题系统上耗时都很低我用本地测试跑过几百个随机树结果完全一致。5.2 边界用例测试清单我在本地会固定跑下面几类用例确保代码不是“碰巧通过”用例结构期望结果空树root None0单节点root TreeNode(5)5单链1 - 2 - 3 - 44普通树[1,2,3,4,5,None,6]15叶子值为0root TreeNode(0)0左右同深[1,2,3,4,5,6,7]22其中“叶子值为0”的用例特别关键。如果你写的判断是if node.val and not node.left and not node.right单节点为0时会被漏判直接返回0但从题目语义来看正确答案也确实是0所以它会错误地“通过”。这就是为什么测试用例不能只看输出还要在代码逻辑层面保证判断依据是结构而不是值。5.3 三种解法复杂度对比解法时间复杂度空间复杂度代码复杂度适用场景两次遍历DFSO(n)O(h)低新手理解思路一次DFS返回元组O(n)O(h)中面试展示状态合并BFS层序O(n)O(w)低树高可能很大时这里的 h 是树高w 是最大层宽度。普通二叉树中 h 和 w 都可能达到 n所以理论最坏情况都是 O(n)。但实际刷题时追求的不只是复杂度还有“思路清楚、不容易写错”以及“赶紧写出能通过的代码”。BFS 版本对初学者最友好一次DFS版本最锻炼递归设计能力两次遍历版本最直白但代码最啰嗦。6. 常见问题与误区的深度排查6.1 全局变量残留问题我最早尝试的版本是递归加全局变量max_depth 0 total 0 def dfs(node, depth): global max_depth, total if not node: return if not node.left and not node.right: if depth max_depth: max_depth depth total node.val elif depth max_depth: total node.val return dfs(node.left, depth 1) dfs(node.right, depth 1)这个思路本身是对的但有个很大的隐患如果写成类方法中的self.max_depth和self.total多次调用同一个实例对象时上一次的结果会残留下来。判题系统通常会每次创建新对象所以不出问题但我在本地连续测试多个用例时发现第二次的答案会把第一次的值加进去越加越大。解决办法是在入口处重置self.max_depth 0 self.total 0或者在嵌套函数里用nonlocal声明并手动归零。这个坑属于典型的“本地测试和在线判题环境不一致”问题不亲身踩一次很难意识到。6.2 递归返回深度忘记加1一次DFS返回(depth, sum)的写法中最隐蔽的错误是返回时忘记加1。比如if l_depth r_depth: return (l_depth, l_sum)这样写返回的深度不包含当前节点这一层一路往上会把整棵树的深度算小。这种错误很麻烦因为它不会让你直接得到0或一个完全离谱的数而是可能在某个节点上比较左右子树深度时产生偏差导致最后把不是最深的叶子也算进去。我建议写完递归后手动用一棵三层满二叉树过一遍叶子返回1父节点返回2根节点返回3。如果根节点最终返回的不是3那一定就是某个地方把加1漏掉了。6.3 节点值等于0时被误判再强调一遍判断叶子只能用结构不能用值。下面这种写法是经典错误if node.val and not node.left and not node.right: ans node.val当叶子节点的值是0时node.val为 False整个 if 块不会执行。这种情况如果整棵树只有一个值为0的节点答案本来应该是0错误代码也返回0反而不容易暴露。但如果有多个叶子比如最深层叶子值是 [0, 3]正确结果应该是3错误代码会由于跳过0而返回3结果碰巧一致。再比如最深层有两个叶子值都是0正确结果是0错误代码也返回0。这导致很多测试用例都无法发现 bug属于“侥幸通过”的典型。所以必须在代码里养成只用not node.left and not node.right判断叶子的习惯。6.4 嵌套函数中的作用域问题在类方法里定义嵌套递归函数时如果希望修改外层局部变量需要声明nonlocal或者用可变容器包一层。比如class Solution: def deepestLeavesSum(self, root): ans 0 def dfs(node, depth): nonlocal ans if not node: return ...如果不写nonlocalPython 会认为ans是一个新的局部变量赋值时会报UnboundLocalError。另一种常见做法是用self.ans这样不受作用域限制但要记得在入口处重置。面试白板编程时这个细节经常被忽略建议提前想好自己习惯用哪种方式。还有一种写法是把 ans 放在长度为1的列表里ans [0] def dfs(...): ans[0] node.val这样也能绕过作用域限制但代码可读性差一些我一般不推荐。7. 本地调试技巧与扩展思考7.1 手动构造二叉树的辅助函数刷题时最痛苦的事情之一是在本地手动构造测试树。我写了一个简单的辅助函数按层序列表构造二叉树方便把题目示例直接转成树对象from collections import deque def build_tree(nodes): if not nodes: return None root TreeNode(nodes[0]) q deque([root]) idx 1 while idx len(nodes): node q.popleft() if nodes[idx] is not None: node.left TreeNode(nodes[idx]) q.append(node.left) idx 1 if idx len(nodes) and nodes[idx] is not None: node.right TreeNode(nodes[idx]) q.append(node.right) idx 1 return root这个函数的逻辑很简单用队列按层扫描每次从队列里取出一个节点然后从列表里取两个元素作为它的左右孩子。列表里的None表示没有孩子。有了这个函数我就可以把题目示例写成root build_tree([1, 2, 3, 4, 5, None, 6]) print(Solution().deepestLeavesSum(root))输出就是15。本地验证速度比直接在浏览器里提交快得多。7.2 打印遍历过程辅助理解如果递归写得很晕我会在递归函数里加打印观察每个节点返回了什么。比如def dfs(node): if not node: return (0, 0) if not node.left and not node.right: return (1, node.val) l_depth, l_sum dfs(node.left) r_depth, r_sum dfs(node.right) print(node.val, l_depth, l_sum, r_depth, r_sum) ...打印出来的每一行能清楚看到左右子树的返回结果。这个方法尤其适合调试“返回深度忘记加1”这类问题。等你把思路理清楚后再把打印去掉。7.3 从这道题出发的变体1302 题本身不难但可以做很多变体练习最深层所有节点的平均值BFS 最后一层累加后除以该层节点个数。最深层叶子节点的个数BFS 最后一层每加一个值就计数。最深层最左侧叶子节点的值BFS 时记录最后一层第一个出队节点。最深层节点中值最大的节点BFS 最后一层用一个变量维护最大值。这些变体的核心逻辑都和原题一致只是最后一层处理方式不同。练完 1302 后可以把“二叉树的层平均值”“二叉树最大深度”“二叉树最小深度”一起刷一遍你会发现层序遍历的框架一脉相承。8. 一点刷题心得8.1 这道题教会我的三件事第一读题要到“等价关系”的层面。“层数最深的叶子节点”和“最后一层节点”是同一个集合这个等价关系直接指向 BFS 解法。很多题目的难点不是代码而是对题面描述的翻译。第二递归返回值可以是一个“状态包”。只返回一个值有时候解决不了问题返回(depth, sum)就能在一次遍历内同时拿到两个信息。这种设计思路比“先全局变量再清零”要优雅得多也更可靠。第三边界条件必须靠“结构判断”不能靠“值判断”。叶子节点用not node.left and not node.right判断不要用node.val判断。节点值是0时后者会让你的代码在最需要正确的时候出错。8.2 给同样在练树的人的建议树的题目特别适合“一题多解”。我强烈建议你拿到题之后不要只满足于一种解法通过而是把两步遍历、一次递归、BFS 三种方法都写一遍。这样练习一次相当于把二叉树的基本功重新梳理了一遍。写的过程中遇到问题也不要立刻看题解先用打印或者构造特殊用例的方式自己排查排查的过程就是长经验的过程。我个人在实际操作中的体会是算法题刷到最后拼的不只是灵感和记忆而是对基础数据结构的熟练度。像 1302 这种看似简单的题反而最能检验你对深度、层数、叶子节点这些基础概念是否真的理解得透。把它彻底吃透后面遇到更复杂的树形 DP 题目你会觉得从容很多。希望这篇记录能帮正在练树专题的你少走几步弯路。