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

2026-03-28 HGNULB 约 8 分钟

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

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

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

题意分析

题目目标：给定一棵二叉树，按从上到下的顺序返回每一层节点值中的最大值，答案数组的长度等于树的高度，第 i 个元素对应深度为 i 的那一层。
核心约束：答案是按"层"聚合的，节点之间只有同层才互相比较，跨层不比较，所以核心是要有一种能明确区分"当前节点属于哪一层"的遍历方式；节点数可达 $5 \times 10^4$，只能线性访问一遍。
边界处理：树可能为空，此时返回空数组而不是 [0]；节点值可以是负数（题目范围包含 $-2^{31}$ 附近），因此每层的初始比较基准不能取 0；只有一个节点时答案是长度为 1 的数组。
实现取舍：需要在遍历中同时掌握两件事——节点的值和它所处的层，只要能把"同一层的节点在同一批被处理"这件事做实，剩下的就只是取最大值。

解法：深度优先搜索

核心思路

最朴素的想法是先求出树高，再对每个深度单独跑一遍遍历筛出该层节点取最大值。这样要遍历 h 遍，代价是 $O(nh)$，链状树退化到 $O(n^2)$，而且每一遍的绝大部分工作都是重复的。
瓶颈在于"层"这个信息被反复重建。观察到：如果按层推进遍历，即把当前层的所有节点一次性取出、处理完再把它们的孩子作为下一层，那么每个节点只被访问一次，层的归属天然就在推进过程中确定了。
由此确定不变量：每轮外层循环开始时，容器 q 里恰好装着当前层的全部节点，不多不少；把当前层的节点数 q.size() 先快照下来，用内层循环消费掉这么多个节点，消费过程中新入队的都是下一层的节点，循环结束后容器里恰好只剩下一层的全部节点，不变量对下一轮继续成立。
每一轮维护一个局部变量 t 表示"本层已处理节点中的最大值"，初始取整型下界而不是 0，逐个用 max 更新；本轮结束时 t 就是该层答案，追加进结果数组。

解题步骤

先判空并直接返回空结果。为什么必须显式处理：后面的第一步是把根入队并访问它的孩子，空树入队会得到一个装着空指针的容器，取值时立刻崩溃。

把根节点入队，进入外层循环，条件是容器非空。为什么这个条件等价于"还有层没处理"：不变量保证容器里装的就是下一个待处理层，空则说明所有层都已处理完毕。

每轮开始时先把 t 初始化为 Integer.MIN_VALUE。为什么不初始化为 0 或根值：节点值可能全为负数，取 0 会让答案错误地变成 0；取根值则跨层污染了本层的比较基准。

用 for (int i = q.size(); i > 0; --i) 固定本轮消费的节点数。为什么必须先把长度快照下来：循环体里会向同一个容器追加下一层的节点，若把 q.size() 直接写进循环条件里反复求值，就会把下一层的节点也卷进本层。

每弹出一个节点，先用它的值更新 t，再把非空的左右孩子入队。为什么是"先取值后扩展"：取值属于当前层的结算，扩展属于为下一层做准备，两者顺序固定才能保证不变量在轮末成立。

内层循环结束后把 t 追加进答案。为什么这一步一定在内层循环之外：只有把本层节点全部消费完，t 才是这一层真正的最大值。

以 具体用例：树 [1, 3, 2, 5, 3, null, 9]（根 1；第二层 3、2；第三层 5、3 是节点 3 的孩子，9 是节点 2 的右孩子）走一遍。第一轮容器为 [1]，快照长度 1，t 从下界更新为 1，入队 3 和 2，答案得 [1]。第二轮容器为 [3, 2]，快照长度 2，弹出 3 使 t = 3 并入队 5、3，弹出 2 使 t 仍为 3 并入队 9，答案得 [1, 3]。第三轮容器为 [5, 3, 9]，快照长度 3，依次更新 t 为 5、5、9，三个节点都没有孩子，答案得 [1, 3, 9]。容器变空，循环结束，返回 [1, 3, 9]。

代码实现

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        if (root == null) {
            return answer;
        }
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int t = Integer.MIN_VALUE;
            for (int i = q.size(); i > 0; --i) {
                TreeNode node = q.poll();
                t = Math.max(t, node.val);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            answer.add(t);
        }
        return answer;
    }
}

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
func largestValues(root *TreeNode) []int {
    var answer []int
    if root == nil {
        return answer
    }
    var q = []*TreeNode{root}
    for len(q) > 0 {
        t := math.MinInt32
        for i := len(q); i > 0; i-- {
            node := q[0]
            q = q[1:]
            t = max(t, node.Val)
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
        answer = append(answer, t)
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$。凭什么：每个节点恰好入队一次、出队一次，出队时只做一次比较和至多两次入队判断，不存在任何节点被二次访问。

空间复杂度：$O(w)$，w 是树的最大层宽，最坏情况下（满二叉树的最后一层）为 $O(n)$。凭什么：容器在任意时刻至多同时存放相邻两层的部分节点，与答案数组一起构成全部额外开销。

关键点总结

"按层聚合"类问题的通用骨架是：外层循环推进层、内层循环用快照长度消费当前层，这一层长度快照是把层边界钉死的唯一手段，换成任何"边遍历边判断深度"的写法都要额外记录深度。

每层的聚合变量必须在层内初始化、层末结算，作用域越紧越不容易被上一层污染，这个模式可以原样迁移到求层和、层平均、层最左值等一整类题目。

聚合极值时初始值要取类型下界而不是 0，凡是题目允许负数就必须这么做；若不想依赖常量，也可以用"本层第一个节点的值"作为初值。

空树要在入口就返回，不要指望后续循环自然跳过——把空指针挡在容器之外，比在容器内到处判空更干净。

面试视角：面试官通常会追问"能不能用递归做"。答案是可以：递归时把深度作为参数传下去，若 depth == answer.size() 就追加一个新层的初值，否则更新已有位置；主动给出这一层等价关系，并指出递归版空间是 $O(h)$、迭代版是 $O(w)$，二者在链状树和满树上各有优势，是这题最好的加分回答。

易错点总结

错误写法：内层循环写成 for (int i = 0; i < q.size(); ++i) → 树 [1, 3, 2] 时第一轮循环体内入队了 3 和 2 使长度变化，条件被重新求值，第二层节点被并入第一层，答案变成 [3] 这样的单元素数组。

错误写法：t 初始化为 0 → 树 [-1, -2, -3] 的答案应为 [-1, -2]，实际得到 [0, 0]，全部负数层被 0 覆盖。

错误写法：t 在外层循环之外只初始化一次 → 树 [5, 1, 2] 的答案应为 [5, 2]，实际第二层继承了上一层的 5，得到 [5, 5]。

错误写法：漏掉 root == null 的判空 → 空树输入时把 null 入队，出队后访问 node.val 直接空指针异常。

错误写法：把空孩子也入队，靠出队时判空跳过 → 空节点被计入本层长度快照，t 的更新逻辑要额外分支，一旦忘记就在访问 node.val 时崩溃；即使不崩，某些实现里空层还会多产出一个答案项。

错误写法：answer.add(t) 写在内层循环里面 → 树 [1, 3, 2] 时第二层产出两次，答案变成 [1, 3, 3]，长度不等于树高。

错误写法：Go 中用 math.MinInt32 却假设节点值可能小于它 → 若变种题把值域放宽到 64 位，初值不够小会让整层答案错误，应改用 math.MinInt64 或首元素初始化。

错误写法：先扩展孩子再用节点值更新 t，同时把 t 的更新写成"用队首元素" → 队首此时已经是下一层的节点，树 [1, 3, 2] 的第一层答案被算成 3。

错误写法：用一个全局 List 按深度下标直接 set 却没先扩容 → 递归改写时对尚不存在的下标调用 set 抛出越界异常，必须先判断 depth == answer.size() 再 add。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	每层结果是完整列表而非聚合值，考察分层收集
103. 二叉树的锯齿形层序遍历	中等	在分层基础上按奇偶层反转方向
199. 二叉树的右视图	中等	每层只取末位元素，聚合规则换成位置而非大小
637. 二叉树的层平均值	简单	聚合量变成和与个数，还要注意求和的溢出
662. 二叉树最大宽度	中等	需要给节点附带层序编号才能算上空位的宽度
1302. 层数最深叶子节点的和	中等	只关心最后一层的聚合结果，可用覆盖式写法简化