LeetCode 1302. 层数最深叶子节点的和

2022-02-24 HGNULB 约 10 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 1302. 层数最深叶子节点的和

题意分析

给一棵二叉树的根节点，求出深度最大的那一层上所有节点的值之和。这里有个容易被名字误导的地方：题目说的是「最深叶子节点」，但深度最大的那一层里，每个节点必然都是叶子（否则它还有孩子，深度就更大了）。所以「最深一层所有节点的和」和「所有最深叶子的和」是同一件事，不需要额外判断某个节点是不是叶子。

要求的量只与深度有关，与节点在树中的左右位置无关。这提示按深度组织遍历——只要能把节点按深度分组，答案就是最后一组的和。同时注意答案只需要最后一组，前面所有层的结果算完就可以丢弃，不需要开数组保存每层的和。

数据范围给到 $10^4$ 个节点，节点值可能为负也可能很大，但题目保证结果在 int 范围内。树可能极度倾斜（退化成一条链），这会让任何按深度递归的写法面临 $10^4$ 层的栈深度。

边界：树可能只有根节点，此时答案就是根的值；根节点为空时应返回 0；某一层可能只有一个节点。

解法：层序遍历按层覆盖答案

核心思路

最直接的想法是先跑一遍求出最大深度 maxDepth，再跑第二遍把深度等于 maxDepth 的节点值加起来。这能过，但要遍历两次树，而且要多维护一个「当前深度」参数。瓶颈在于：第一次遍历其实已经按顺序碰到过每一层了，只是没把结果留下来。

关键观察是：如果能保证按深度从小到大处理节点，并且能识别出每一层的分界，那么每算完一层就把答案覆盖成这一层的和，遍历结束时留在答案里的自然就是最深那一层的和——根本不需要事先知道最大深度是多少。这把两遍遍历压成了一遍，也省掉了显式的深度变量。

「按深度从小到大处理」由队列的先进先出天然保证：根先入队，出队时把它的孩子追加到队尾，于是队列里始终是「当前层剩余节点 + 已产生的下一层节点」，深度小的永远排在前面。

剩下的问题只有一个：怎么知道当前层在哪里结束？这里用的不变量是——每一轮外层循环开始时，队列里恰好装着且只装着同一层的全部节点。有了这条不变量，进入循环体时先把 size = queue.size() 抄下来，接下来正好弹 size 次就把这一层清空；而这 size 次弹出过程中追加到队尾的，全是下一层的节点。一轮结束后队列里又恰好是下一层的全部节点，不变量得以维持。

levelSum 在每轮开头清零、循环体内累加，循环退出后它保留的就是最后一轮（即最深一层）的值。这个「用变量覆盖而非用容器收集」的手法，是所有「只要最后一层 / 最后一个」类问题的通用简化。

解题步骤

根为空直接返回 0：这一步必须有。若不判空就把 root 入队，后面弹出时会对空指针取 val。返回 0 也符合「空树没有任何叶子，和为 0」的语义。

根节点入队，levelSum 初始化为 0：入队根节点让不变量在第一轮成立（队列里恰好是第 0 层的全部节点）。

外层 while (!queue.isEmpty())：队列空意味着再没有下一层了，这正是「已经处理完最深一层」的信号。用队列是否为空作终止条件，比先算最大深度再比较要简洁得多。

循环体第一行先取 size = queue.size()：必须在弹出任何节点之前取。一旦开始弹出并追加孩子，queue.size() 就同时混入了两层的节点，再取就分不清层边界了。这是本题唯一的技术要点。

levelSum = 0 清零：放在内层循环之前，等价于「丢弃上一层的结果」。清零位置若放到外层循环之外，累加的就是全树节点和而不是某一层的和。

内层固定循环 size 次：每次弹出一个节点、累加 node.val，再把非空的左右孩子入队。用固定次数而不是「弹到队列空」，正是靠 size 把本层与下一层隔开。

只把非空孩子入队：避免队列里混入 null，也就不需要在弹出时再判空。

循环结束后返回 levelSum：此时它保存的是最后一轮的和。注意 levelSum 必须声明在 while 之外，否则出了循环就取不到。

以下面这棵树走一遍（根为 1，左子树 2 带两个孩子 4、5，右子树 3 带一个右孩子 6），答案应为 4 + 5 + 6 = 15。

初始：队列 [1]，levelSum = 0。

第一轮：size = 1，levelSum 清零。弹出 1，levelSum = 1，把 2、3 入队。轮末队列为 [2, 3]——恰好是第 1 层的全部节点，不变量成立。

第二轮：size = 2，levelSum 清零。弹出 2，levelSum = 2，入队 4、5；弹出 3，levelSum = 5，3 无左孩子只入队 6。轮末队列为 [4, 5, 6]。注意这里 size 在轮首就被固定成 2，所以尽管队列中途涨到了 4 个元素，内层也只弹 2 次，没有把第 2 层的节点误当成第 1 层处理。

第三轮：size = 3，levelSum 清零。依次弹出 4、5、6，levelSum 变成 4、9、15；三者都没有孩子，队列不再增长。轮末队列为空。

外层循环条件不满足，退出，返回 levelSum = 15。可以看到第一轮算出的 1 和第二轮算出的 5 都被后来的清零操作丢弃了，这正是「覆盖式」写法想要的效果。

代码实现

class Solution {
    // 层序遍历天然按深度推进，每处理完一层就用当前层节点值之和覆盖答案。
    public int deepestLeavesSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int levelSum = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            levelSum = 0;

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return levelSum;
    }
}

func deepestLeavesSum(root *TreeNode) int {
    // 层序遍历天然按深度推进，每处理完一层就用当前层节点值之和覆盖答案。
    if root == nil {
        return 0
    }

    queue := []*TreeNode{root}
    levelSum := 0

    for len(queue) > 0 {
        levelSum = 0
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            levelSum += node.Val

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }

    return levelSum
}

复杂度分析

时间复杂度：$O(n)$，其中 n 是节点数。凭什么：每个节点恰好入队一次、出队一次，出队时做的是一次加法和两次判空入队，都是常数操作。

空间复杂度：$O(w)$，w 是树的最大宽度，最坏为 $O(n)$。凭什么：队列在任意时刻最多同时存放相邻两层的节点，满二叉树的最后一层就有约 n / 2 个节点。levelSum、size 是常数级，不影响量级。

关键点总结

「只要最后一层的聚合值」这类需求，用一个变量按层覆盖即可，不必收集所有层再取末尾，也不必先求最大深度再跑第二遍——这是层序遍历模板最常见的一种裁剪。

层序遍历分层的唯一正确姿势是「在弹出任何节点之前先固定本层大小」，因为队列长度在弹出过程中会被下一层污染。面试写 BFS 时这一行被盯得最紧。

「每轮循环开始时队列恰好装着一整层」是这段代码的循环不变量，能主动把它讲出来，比复述代码更能说明你真的理解分层机制。

用队列是否为空作为终止条件，天然回答了「最深一层在哪」，省掉一个显式的深度计数器——凡是只关心相对顺序而非绝对深度的题都可以这么省。

树类题目在 $10^4$ 量级下要留意退化成链的情形：BFS 的空间取决于宽度，链形树反而只占 $O(1)$；而递归写法此时栈深达 $10^4$，这是选 BFS 的一个实际理由。

易错点总结

忘记先取 size，把内层写成 while (!queue.isEmpty())：上面那棵树第一轮就会把 1、2、3、4、5、6 全部弹完，levelSum 变成全树和 21，且外层只跑一轮。

在弹出若干节点之后才取 size：同一棵树第二轮取到的 size 可能已经是 3 或 4，会把第 2 层的节点计入第 1 层，返回 9 之类的错值。

levelSum 清零写在 while 之外：上面那棵树会返回 1 + 5 + 15 = 21，即全树节点和。

levelSum 声明在 while 内部：Java 里编译期就报「无法解析符号」，Go 里返回的是外层那个始终为 0 的变量。

漏掉 root == null 的判断：传入空树时先 offer(null)，第一轮弹出后访问 node.val 抛空指针异常（Go 是 nil 解引用 panic）。

入队时不判空孩子：树 [1,2]（根只有左孩子）会把 null 压进队列，下一轮弹出时对 null 取 val 崩溃。

用栈（DFS 前序）代替队列却仍按「覆盖」的写法：同一棵树里节点不再按深度分组，levelSum 保存的是最后被访问的若干节点，返回 6 而不是 15。

判断节点是否叶子后才累加：树 [1,2,3,4,5,null,6] 里第 1 层的 2、3 不是叶子被跳过没问题，但若把「叶子」判断和「最深」混为一谈，[1,2,null,3] 这种链形树里深度 1 的节点 2 不是叶子、深度 2 的 3 才是，写成「累加所有叶子」会返回 3 + 其它浅层叶子之和。

用 LinkedList 却调用 pop() 而非 poll()：pop() 从头部弹出对 LinkedList 恰好等价，但换成 ArrayDeque 并用 push 入队时就变成了栈语义，层次结构被打乱。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	要保留每一层的完整结果，不能像本题这样用一个变量覆盖
107. 二叉树的层序遍历 II	中等	自底向上输出，可在收集完成后反转，或直接头插到结果列表
103. 二叉树的锯齿形层序遍历	中等	层内顺序按奇偶交替，用双端队列或对偶数层反转，遍历顺序本身不变
199. 二叉树的右视图	中等	每层只取最后一个节点，判断依据是内层下标是否等于 `size - 1`
513. 找树左下角的值	中等	同样是「最深一层」，但取的是该层第一个节点，可用右孩子先入队的技巧简化
637. 二叉树的层平均值	简单	每层求和后还要除以 `size`，且累加要用 `long` 防溢出
515. 在每个树行中找最大值	中等	层内聚合从求和换成取最大值，初值需设为极小而非 0，否则负数用例出错
104. 二叉树的最大深度	简单	只数层数不聚合节点值，是本题「隐式深度」思路的最小原型
111. 二叉树的最小深度	简单	BFS 碰到第一个叶子就返回，与本题必须走到最后一层恰好相反
662. 二叉树最大宽度	中等	队列里要额外带上完全二叉树编号，靠层首层尾编号之差算宽度
958. 二叉树的完全性检验	中等	反而要把 `null` 入队，靠「空节点之后不能再出现非空节点」判定完全性
429. N 叉树的层序遍历	中等	孩子数不定，入队处改为遍历 `children` 列表，分层逻辑完全照搬
面试题 04.03. 特定深度节点链表	中等	每层结果串成链表而非数组，需要在层内维护尾指针
LCR 045. 找树左下角的值	中等	与 513 同题，可直接套用
LCR 046. 二叉树的右视图	中等	与 199 同题，可直接套用