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

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 2-5 字节
标签
深度优先搜索 树 广度优先搜索 二叉树

题目描述

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

image-20260928224524406

image-20260928224524408

题意分析

对二叉树的每一层分别求节点值的最大值，再按从根到叶的层次顺序返回。每层只产生一个答案，节点所处的左右位置不影响数值比较。

节点值可以为负数，甚至等于 32 位整数最小值；空树没有任何层，直接返回空结果。要先准确划分层，再在层内做最大值统计。

解法：层序遍历

核心思路

[!blue]

使用队列进行层序遍历。每轮开始时，队列中尚未处理的节点恰好属于同一层，先将它们的数量保存为 size，随后只处理这 size 个节点。处理时加入的孩子在队尾，属于下一层，不能混入本轮统计。

本层最大值从题目允许的最小节点值开始。每处理一个节点就更新最大值，于是它始终等于“已扫描的本层节点中的最大值”；扫描完 size 个节点后，就得到整层答案，追加一次即可。下一层需要重新初始化，不能继承上一层的最大值。

Java 出队时删除已处理节点，所以本层数量就是 queue.size()。Go 用 head 标记下一个未处理位置，已处理节点仍保留在切片前部，因此本层数量应为 len(queue)-head。两种实现都在开始时冻结这个数量，保证本层结束后剩余待处理部分正好是下一层。

即使一整层的值都等于最小整数，初始最大值也已经正确，无需强求比较过程中一定发生更新。队列中没有待处理节点时，全部层都已输出，遍历结束。

解题步骤

  1. 空树直接返回；否则将根节点加入队列。
  2. 保存当前未处理节点数 size，将本层最大值重置为 32 位整数最小值。
  3. 恰好读取 size 个节点，逐个更新最大值，并将非空孩子追加到队尾。
  4. 本层循环结束后追加最大值，再处理下一层，直到没有未处理节点。

代码实现

// 每一层扫描节点值，取最大值加入结果。
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$ 是节点数。每个节点入队并处理一次，最大值更新为常数时间。
  • 空间复杂度：不计输出，Java 活动队列占 $O(w)$，其中 $w$ 为最大层宽；Go 当前实现保留已处理的切片前缀，累计占 $O(n)$。结果每层存一个数，占 $O(h)$，其中 $h$ 为树高。

关键点总结

[!green]

  • 分层数量解决“哪些节点属于本层”，最大值变量解决“这层已经扫描过的节点中谁最大”。
  • 用合法下界初始化，使全负数层和最小整数节点都能正确参与比较。
  • 结果只在整层结束时追加，每层的聚合状态也只在下一层开始时重置。

易错点总结

[!yellow]

  • 最大值从零开始，会错误处理全负数的一层。
  • 内层条件使用变化中的队列长度，会将不同层混在一起。
  • 每处理一个节点就追加，会使一层出现多个结果。

相似题目

题目 难度 关联与区别
1161. 最大层内元素和 中等 同样对每层聚合，原题求层和并比较层号，本题逐层取节点最大值。
199. 二叉树的右视图 中等 同样输出每层一个代表节点，右视图按位置取最右者，本题按数值取最大者。
102. 二叉树的层序遍历 中等 按层遍历并在同一层内聚合；本题每层只保留最大节点值，该题保留每层全部节点。
103. 二叉树的锯齿形层序遍历 中等 按层遍历并在同一层内聚合；本题每层只保留最大节点值，该题交替调整每层输出方向。
107. 二叉树的层序遍历 II 中等 按层遍历并在同一层内聚合；本题每层只保留最大节点值，该题把自顶向下的层结果反转。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/02128401
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！