LeetCode 515. 在每个树行中找最大值

2026-06-21 HGNULB 约 10 分钟

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

分类

题目描述

✅ 515. 在每个树行中找最大值

题意分析

给一棵二叉树，要求返回一个数组，第 i 个元素是树的第 i 层（根为第 0 层）中所有节点值的最大值。也就是说，答案的长度等于树的高度，每一层贡献一个数。

题目问的是「按层聚合」，这就要求遍历过程必须能准确区分哪些节点属于同一层。普通的层序遍历只保证节点按层次顺序被访问，但如果不做额外处理，队列里前一层和后一层的节点是混在一起的，无法知道分界点在哪。如何切分层次，是本题唯一真正的技术点。

节点值的范围是 $[-2^{31}, 2^{31}-1]$，可以是负数。这个约束直接否定了「把每层最大值初始化为 0」的写法——一整层全是负数时会返回错误的 0。初始值必须取 Integer.MIN_VALUE 这种真正的下界，或者用该层第一个节点的值。这是本题最容易翻车的地方，也是它被定为中等而不是简单的原因之一。

树可以为空，此时应返回空数组而不是 [某个值]。另外树可能退化成一条链，每层只有一个节点，答案就是从根到叶的那串值。

从数据形态看，「按层输出」几乎就是在点名要求宽度优先遍历；但用深度优先配合层号索引也能做到，后面会在关键点里提一句权衡。

解法：层序遍历

核心思路

先看一个不加处理的宽度优先遍历：用队列，弹出一个节点就把它的孩子推进去。这样能按从上到下、从左到右的顺序访问所有节点，但队列里同时躺着两层的节点，弹出时无从判断当前节点属于哪一层，也就无法在层与层之间切开去求最大值。这是瓶颈。

一个笨办法是给每个节点额外存一个层号，入队时带上，弹出时比较层号是否变化。它可行，但要么改节点结构、要么额外开一个队列存层号，都不够干净。

关键观察是：在开始处理某一层之前的那个瞬间，队列里的元素恰好就是这一层的全部节点，一个不多一个不少。因为上一层的节点已经全部弹完，而下一层的节点还没被推入。所以只要在这个时刻把 queue.size() 取出来存进 size，然后严格只弹出 size 次，就精确地处理完了一层——期间新推入的孩子属于下一层，不会被这一轮的内层循环碰到。

这就是「按层批处理」的写法。维持的不变量是：每次进入外层 while 时，队列中的元素恰好构成树的某一整层，且顺序为从左到右。初始时队列只有根节点，构成第 0 层，成立；内层循环弹出恰好 size 个节点并把它们所有非空孩子按左右顺序推入，退出时队列里正好是下一层的全部节点，不变量得以维持。当某一层没有任何孩子时队列变空，外层循环终止。

有了这个不变量，求每层最大值就是顺带的事：内层循环开始前把 max 置为下界，循环中对每个弹出的节点做一次比较，内层结束后 max 就是这一层的最大值，直接追加进结果。

max 的初值必须是 Integer.MIN_VALUE 而不是 0，因为节点值可以为负；由于每一层至少有一个节点（否则外层循环就结束了），这个下界一定会被至少一次比较更新掉，不会有「下界被原样写进结果」的风险。

解题步骤

空树直接返回空列表：root == null 时不存在任何层，答案为空数组。这一步同时保证了后面 queue.offer(root) 不会把 null 推进队列，避免内层循环取 node.val 时空指针。

建队列并推入根节点：这样第一轮外层循环时队列恰好是第 0 层，不变量从一开始就成立。Java 用 ArrayDeque 而非 LinkedList，前者常数更小；Go 用切片加读游标 head 模拟队列，避免频繁的切片头部截断。

外层循环条件 !queue.isEmpty()：队列空意味着上一层没有产生任何孩子，遍历结束。

进入外层循环后立刻用 size = queue.size() 冻结本层节点数：这一行是全题的核心。必须在弹出任何节点之前取，且必须存进局部变量——如果在内层循环条件里直接写 i < queue.size()，队列大小会随着孩子入队而变化，层的边界立刻失效。

把 max 初始化为 Integer.MIN_VALUE：节点值可能全为负，用 0 会得到错误结果。Go 里对应写 -1 << 31。

内层循环恰好执行 size 次：每次弹出一个节点、用它的值更新 max，再把非空的左右孩子按顺序推入队列。判断 != null 才入队，是为了不让空指针进入队列破坏后续的 node.val 访问。

内层结束后把 max 追加进结果：此时这一层的所有节点都已比较过。追加的时机必须在内层循环之外、外层循环之内，放错位置会导致每个节点各产生一个结果。

返回结果列表：外层循环退出时所有层都已处理完毕。

以样例树走一遍：根为 1，左孩子 3、右孩子 2；节点 3 的左孩子 5、右孩子 3；节点 2 的右孩子 9。答案应为 [1, 3, 9]。

初始：队列 [1]，结果 []。

第一轮外层：size = 1，max = MIN。弹出 1，max = 1；推入它的孩子 3 和 2。内层结束，队列变成 [3, 2]，结果变成 [1]。注意此刻队列恰好是完整的第 1 层。

第二轮外层：size = 2，max = MIN。第一次弹出 3，max = 3，推入 5 和 3；第二次弹出 2，max 保持 3（2 < 3），推入 9。内层恰好跑了 2 次就停，尽管此时队列里已经有 3 个元素——这正是冻结 size 的价值。队列变成 [5, 3, 9]，结果变成 [1, 3]。

第三轮外层：size = 3，max = MIN。依次弹出 5（max = 5）、3（max 仍 5）、9（max = 9），三者都没有孩子，无新元素入队。队列变空，结果变成 [1, 3, 9]。

外层循环条件不成立，返回 [1, 3, 9]，正确。

再验证负数用例：一棵只有根 -5 和左孩子 -9 的树。第一轮 max 从 MIN 更新为 -5，第二轮更新为 -9，返回 [-5, -9]。如果 max 初值写成 0，会错误地返回 [0, 0]。

代码实现

// 每一层扫描节点值，取最大值加入结果。
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

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

        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;

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

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

            res.add(max);
        }

        return res;
    }
}

// 每一层扫描节点值，取最大值加入结果。
func largestValues(root *TreeNode) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }

    queue := []*TreeNode{root}
    for head := 0; head < len(queue); {
        size := len(queue) - head
        maxVal := -1 << 31

        for i := 0; i < size; i++ {
            node := queue[head]
            head++

            if node.Val > maxVal {
                maxVal = node.Val
            }

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

        res = append(res, maxVal)
    }

    return res
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是节点总数。每个节点恰好入队一次、出队一次，出队时做一次比较和两次空判断，全是常数操作。

空间复杂度：$O(w)$，其中 $w$ 是树的最大宽度，即队列在任一时刻的峰值长度。完全二叉树时最后一层约有 $n/2$ 个节点，所以最坏是 $O(n)$；退化成链时每层只有一个节点，只需 $O(1)$。返回的结果数组长度等于树高，属于必要输出不计入。

关键点总结

进入每轮循环时先冻结 queue.size()，是把「混着两层的队列」切成整齐层次的唯一关键；这一行几乎是所有按层聚合题（右视图、锯齿遍历、层平均值、最大宽度）的共同骨架，值得当成模板背下来。

不变量「每次外层循环开始时队列恰为完整一层」比代码本身更该说给面试官听——它同时解释了为什么内层跑 size 次、为什么新入队的孩子不会被误算。

聚合初值必须取自数据的真实下界：值域含负数时用 0 初始化最大值是经典错误。更稳妥的写法是用该层第一个节点的值作初值，能彻底绕开值域讨论。

空判断放在入队前而不是出队后，能保证队列里永远没有 null，减少一处潜在的空指针；这是宽度优先遍历的通用卫生习惯。

本题也可以用深度优先做：递归时带上层号 depth，若 depth == res.size() 就追加、否则更新 res.get(depth)。时间同为 $O(n)$，空间是 $O(h)$ 递归栈，在树很宽时反而更省。面试时能主动给出这个替代方案并比较两者的空间取舍，是加分项。

易错点总结

max 初值写成 0：树只有根 -5 时会返回 [0] 而不是 [-5]，任何整层全负的用例都会错。

内层循环条件直接写 i < queue.size()：孩子入队会让 size 不断变大，第一轮就可能把第 1 层的节点也算进第 0 层，样例树会返回 [3, ...] 之类的错乱结果，甚至一轮跑完整棵树。

size 在弹出若干节点之后才取：层的边界整体后移，[1,3,2] 这棵树会把节点 2 划进下一层，结果长度和数值全错。

res.add(max) 写在内层循环里面：每个节点都产生一个结果，样例树会返回 6 个元素而不是 3 个。

忘记 root == null 的判断：root 为 null 时被推进队列，内层取 node.val 立刻抛空指针。

入队前不判断孩子是否为空：null 进了队列，下一层弹出时访问 node.val 崩溃；即使用 if (node == null) continue 补救，size 里也混进了不存在的节点，层大小失真。

用 LinkedList 的 remove() 而在空队列上调用：内层循环次数若因上面的错误多跑一次，ArrayDeque.poll() 返回 null 后取 .val 空指针，remove() 则直接抛 NoSuchElementException。

Go 里用 queue = queue[1:] 逐个截断切片：功能正确但底层数组无法回收，长链树上内存持续增长；用读游标 head 才是稳妥写法。

误以为答案长度等于节点数或叶子数：答案长度必须等于树高，样例树 3 层就是 3 个数，多输出或少输出都会判错。

用先序遍历直接取每层第一个遇到的节点值：那求的是最左侧的值而不是最大值，[1,3,2,5,3,null,9] 会返回 [1,3,5] 而不是 [1,3,9]。

DFS 写法里用 res.set(depth, ...) 却没先判断该层是否已存在：第一次到达新的一层时索引越界，必须先 add 再 set。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	每层输出全部节点值而非聚合成一个数，是本题骨架的最裸形态
637. 二叉树的层平均值	简单	聚合函数换成求和除以 `size`，求和要用 `long` 防溢出
199. 二叉树的右视图	中等	只取每层最后一个节点，用 `i == size - 1` 判断即可
LCR 046. 二叉树的右视图	中等	与 199 同题
513. 找树左下角的值	中等	只要最后一层的第一个值，可反向入队孩子后直接取最后弹出的节点
LCR 045. 找树左下角的值	中等	与 513 同题
103. 二叉树的锯齿形层序遍历	中等	奇数层需反向收集，用双端队列头插比整体反转更省一次遍历
107. 二叉树的层序遍历 II	中等	层次结果需自底向上，收集时头插或最后整体反转
1302. 层数最深叶子节点的和	中等	只需最后一层的和，可让每层的和覆盖前一层，无需保存全部层
662. 二叉树最大宽度	中等	空位也要计入宽度，需给节点编号并注意深链时编号溢出
958. 二叉树的完全性检验	中等	反其道而行，空节点也入队，一旦遇空后又出现非空即判否
429. N 叉树的层序遍历	中等	孩子数量不定，内层要遍历 `children` 列表而非固定左右两支
LCR 044. 在每个树行中找最大值	中等	与本题同题，可直接套用
剑指 Offer 32 - I. 从上到下打印二叉树	中等	输出拉平成一维数组，反而不需要冻结 `size` 分层
剑指 Offer 32 - II. 从上到下打印二叉树 II	简单	与 102 同题
剑指 Offer 32 - III. 从上到下打印二叉树 III	中等	与 103 同题
面试题 04.03. 特定深度节点链表	中等	每层结果要组装成链表，需在层内维护尾指针边遍历边接