LeetCode LCR 044. 在每个树行中找最大值
题目描述
题意分析
按从上到下的顺序，返回二叉树每一层的最大节点值。不同层分别取最大值，空树返回空列表。节点值可能为负数，每层最大值不能从 $0$ 开始比较。
解法：BFS 逐层取最大值
核心思路
[!blue]
使用队列按层遍历。每轮开始时，队列恰好保存当前层的全部节点；先记录此时的队列长度，本轮只弹出这么多个节点。处理过程中加入的孩子都属于下一层，排在尚未处理的当前层节点后面，不会在本轮被弹出。
当前层处理完后，队列中恰好只剩下一层的全部节点，所以下一轮仍满足相同条件。这样无需为节点额外记录深度，也能把同层节点放在同一次循环中比较。
每层重新将
t初始化为合法节点值的下界。每取出一个节点就用max更新，处理完本层的固定数量后，t就是这一层的最大值，再向结果追加一次。即使整层都是负数，初始下界也不会把答案错误抬高。
解题步骤
- 创建空结果；根为空时直接返回，否则将根入队。
- 每层开始时固定队列长度，并将本层最大值初始化为整型下界。
- 弹出该数量的节点，更新本层最大值，将非空孩子加入队尾。
- 本层结束后追加最大值，再处理下一层。
- 队列为空时返回结果，层的处理顺序就是答案要求的从上到下顺序。
代码实现
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;
}
}
import (
"math"
)
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(h)$ 空间，$h$ 为树高；计入输出时为 $O(w+h)$。
关键点总结
[!green]
- 在加入下一层节点之前固定本层长度，才能保持层与层分开。
- 每层独立初始化和更新最大值，不继承上一层的结果。
- 一层处理完才向答案追加一次，输出数量等于非空层数。
易错点总结
[!yellow]
- 在循环条件中不断读取变化后的队列长度，会混入下一层节点。
- 本层最大值从 $0$ 开始，会错误处理全负数层。
- 每弹出一个节点就追加结果，会把一层拆成多项输出。
- 当前实现先处理空根，避免把空节点加入队列后访问其值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1161. 最大层内元素和 | 中等 | 同样对每层聚合，原题求层和并比较层号，本题逐层取节点最大值。 |
| 199. 二叉树的右视图 | 中等 | 同样输出每层一个代表节点，右视图按位置取最右者，本题按数值取最大者。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！