LeetCode 515中等树/BFS
在每个树行中找最大值 图解题解
这道题到底在问什么
给定二叉树的根,返回一个数组:第 i 个元素是第 i 层(从根开始数)所有节点值里的最大值。
- 输入
- [1,3,2,5,3,null,9]
- 输出
- [1,3,9]
- 输入
- 空树 []
- 输出
- []
最优解：一步一步想明白
- 3记住「队列按层展开,每层扫一遍取最大」,下面逐帧套它。
- 4按深度分层先找感觉:同一深度的节点属于同一层。根 50 是第 0 层,孩子 30、80 是第 1 层,再往下 60、20、75、40 是第 2 层。我们要在每一层里挑出最大值。
- 5本层 1 个节点进入第 0 层,队列里是 [50]。先把这一整层从左到右扫一遍,边扫边更新「本层最大」。
- 6看 50从队首取出 50(红),它是本层第一个节点,先把本层最大记成 50(金色标出)。
- 750 → 30,8050 看完了。把它的非空孩子 30、80(蓝色)加入下一层,目前下一层攒到了 [30、80]。
- 8第 0 层取 50第 0 层整层扫完,最大值是 50(金色标出),记进答案。现在各层最大是 [50]。下一层 [30、80] 已就绪,继续。
- 9本层 2 个节点进入第 1 层,队列里是 [30、80]。先把这一整层从左到右扫一遍,边扫边更新「本层最大」。
- 10看 30从队首取出 30(红),它是本层第一个节点,先把本层最大记成 30(金色标出)。
- 1130 → 60,2030 看完了。把它的非空孩子 60、20(蓝色)加入下一层,目前下一层攒到了 [60、20]。
- 12看 80看节点 80(红):它比当前最大 30 还大,本层最大更新成 80,金色标记移到它身上。
- 1380 → 75,4080 看完了。把它的非空孩子 75、40(蓝色)加入下一层,目前下一层攒到了 [60、20、75、40]。
- 14第 1 层取 80第 1 层整层扫完,最大值是 80(金色标出),记进答案。现在各层最大是 [50、80]。下一层 [60、20、75、40] 已就绪,继续。
- 15本层 4 个节点进入第 2 层,队列里是 [60、20、75、40]。先把这一整层从左到右扫一遍,边扫边更新「本层最大」。
- 16看 60从队首取出 60(红),它是本层第一个节点,先把本层最大记成 60(金色标出)。
- 1760 是叶子60 是叶子,没有孩子可加,下一层暂时还是 [空]。
- 18看 20看节点 20(红):它没有超过当前最大 60,本层最大保持 60 不变。
- 1920 是叶子20 是叶子,没有孩子可加,下一层暂时还是 [空]。
- 20看 75看节点 75(红):它比当前最大 60 还大,本层最大更新成 75,金色标记移到它身上。
- 2175 是叶子75 是叶子,没有孩子可加,下一层暂时还是 [空]。
- 22看 40看节点 40(红):它没有超过当前最大 75,本层最大保持 75 不变。
- 2340 是叶子40 是叶子,没有孩子可加,下一层暂时还是 [空]。
- 24第 2 层取 75第 2 层整层扫完,最大值是 75(金色标出),记进答案。现在各层最大是 [50、80、75]。没有下一层了,BFS 即将结束。
- 25答案 = [50,80,75]每一层的最大值依次是 [50、80、75]。回头看,就是一遍标准的按层 BFS,每层从左到右扫一遍取最大,一次遍历就出全部答案,时间 O(n)。
⚠️ 容易写错的地方
✗ 错：best 初始化成 0
✓ 对：best 初始化成极小值(如负无穷)
节点值可能为负,初始化成 0 会让全是负数的层算出错误的 0
✗ 错：只看每层最后一个节点
✓ 对：从左到右扫完整层再定最大
每层最大不一定在最右(本例第 2 层最大 75 就在中间),必须比较整层
✗ 错：不按层划界、所有节点混比
✓ 对：用进入这轮时的队列长度框定当前层
不划界就会把不同层的节点混在一起,算不出「每层」的最大
完整代码（Python / C++ / Java）
Python
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
q, ans = [root], []
while q:
ans.append(max(n.val for n in q))
q = [c for n in q for c in (n.left, n.right) if c]
return ansC++
#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: vector<int> largestValues(TreeNode* root){ if(!root)return{}; queue<TreeNode*> q; q.push(root); vector<int> ans; while(!q.empty()){ int best=INT_MIN; for(int sz=q.size();sz--;){ auto n=q.front(); q.pop(); best=max(best,n->val); if(n->left)q.push(n->left); if(n->right)q.push(n->right);} ans.push_back(best);} return ans;} };Java
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution { public List<Integer> largestValues(TreeNode root){ ArrayList<Integer> ans=new ArrayList<>(); if(root==null)return ans; Queue<TreeNode> q=new ArrayDeque<>(); q.offer(root); while(!q.isEmpty()){ int best=Integer.MIN_VALUE; for(int sz=q.size();sz>0;sz--){ TreeNode n=q.poll(); best=Math.max(best,n.val); if(n.left!=null)q.offer(n.left); if(n.right!=null)q.offer(n.right);} ans.add(best);} return ans;} }复杂度
时间
O(n)
每个节点恰好出队、入队一次,扫描时也只看一次,n 是节点数
空间
O(w)
w 是树的最大宽度,队列最坏要同时装下最宽一层(可达 n/2 量级)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 在每个树行中找最大值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
用 DFS 能做吗?+
能。DFS 时多带一个参数表示当前深度 depth,维护一个数组 res;每访问一个节点,如果 depth 等于 res 的长度说明到了新的一层,就把当前值 push 进去,否则用 res[depth] = max(res[depth], 值) 更新这一层的最大。前序、后序都行,只要保证每个节点都按它的深度更新对应位置即可。
这类「按层」的题还有哪些变体?+
把「取最大」换成别的聚合就是一系列题:每层平均值、每层最右节点(二叉树的右视图)、之字形层序、每层节点和、最小深度(第一个叶子所在层)等。核心都是这套「队列按层展开」的 BFS 框架,只是每层做的事不同。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 在每个树行中找最大值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。