最大层内元素和 图解题解
这道题到底在问什么
- 输入
- [1,7,0,7,-8]
- 输出
- 2
- 输入
- [1]
- 输出
- 1
最优解：一步一步想明白
- 3记住「队列按层展开,每层求和、和更大才换最佳层号」,下面逐帧套它。
- 4按深度分层先找感觉:同一深度的节点属于同一层。根 1 是第 1 层,孩子 7、0 是第 2 层,再往下 7、-8 是第 3 层。我们要算每一层的和,挑和最大的那一层。
- 5本层 1 个节点进入第 1 层,队列里是 [1]。先把这一整层从左到右扫一遍,边扫边把值累加成本层的和。
- 6加上 1从队首取出 1(红色高亮),把它加进本层的和:0 加 1 得到 1。
- 71 → 7,01 加完了。把它的非空孩子 7、0(蓝色)加入下一层,目前下一层攒到了 [7、0]。
- 8第 1 层和 1第 1 层扫完,本层和是 1。它是第一层,直接成为目前的最大层和,最佳层号记为第 1 层。
- 9本层 2 个节点进入第 2 层,队列里是 [7、0]。先把这一整层从左到右扫一遍,边扫边把值累加成本层的和。
- 10加上 7从队首取出 7(红色高亮),把它加进本层的和:0 加 7 得到 7。
- 117 → 7,-87 加完了。把它的非空孩子 7、-8(蓝色)加入下一层,目前下一层攒到了 [7、-8]。
- 12加上 0从队首取出 0(红色高亮),把它加进本层的和:7 加 0 得到 7。
- 130 是叶子0 是叶子,没有孩子可加,下一层暂时还是 [7、-8]。
- 14第 2 层和 7第 2 层扫完,本层和是 7。7 比之前的最大 1 更大,最佳层号更新成第 2 层。
- 15本层 2 个节点进入第 3 层,队列里是 [7、-8]。先把这一整层从左到右扫一遍,边扫边把值累加成本层的和。
- 16加上 7从队首取出 7(红色高亮),把它加进本层的和:0 加 7 得到 7。
- 177 是叶子7 是叶子,没有孩子可加,下一层暂时还是 [空]。
- 18加上 -8从队首取出 -8(红色高亮),把它加进本层的和:7 加上负数 -8 得到 -1。
- 19-8 是叶子-8 是叶子,没有孩子可加,下一层暂时还是 [空]。
- 20第 3 层和 -1第 3 层扫完,本层和是 -1。-1 没有超过之前的最大 7(在第 2 层),最佳层号保持第 2 层不变。 队列已空,BFS 即将结束。
- 21答案 = 第 2 层三层的和依次是 1、7、-1,最大的是 7,出现在第 2 层,所以答案是 2(金色标出这一层)。回头看,就是一遍标准的按层 BFS,每层求和、和更大才换最佳层号,一次遍历就出答案,时间 O(n)。
⚠️ 容易写错的地方
✗ 错：best 初始化成 0
✓ 对：best 初始化成极小值(如负无穷)
节点值可能为负,某层和全为负时初始化成 0 会让答案错乱
✗ 错：平局时返回较大的层号
✓ 对：只在「严格更大」时更新最佳层号
题目要求并列最大返回最小层号,用严格大于就能让先出现的层(层号更小)保留下来
✗ 错：层号从 0 开始
✓ 对：层号从 1 开始(根是第 1 层)
本题层号定义是从 1 起,从 0 起会整体差 1
完整代码（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 maxLevelSum(self, root: Optional[TreeNode]) -> int:
q, level, best_level, best = [root], 1, 1, -10**18
while q:
s = sum(n.val for n in q)
if s > best:
best, best_level = s, level
q = [c for n in q for c in (n.left, n.right) if c]
level += 1
return best_levelC++
#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: int maxLevelSum(TreeNode* root){ queue<TreeNode*> q; q.push(root); int level=1,bestLevel=1; long long best=LLONG_MIN; while(!q.empty()){ long long sum=0; for(int sz=q.size();sz--;){ auto n=q.front(); q.pop(); sum+=n->val; if(n->left)q.push(n->left); if(n->right)q.push(n->right);} if(sum>best){best=sum; bestLevel=level;} level++; } return bestLevel; } };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 int maxLevelSum(TreeNode root){ Queue<TreeNode> q=new ArrayDeque<>(); q.offer(root); int level=1,bestLevel=1; long best=Long.MIN_VALUE; while(!q.isEmpty()){ long sum=0; for(int sz=q.size();sz>0;sz--){ TreeNode n=q.poll(); sum+=n.val; if(n.left!=null)q.offer(n.left); if(n.right!=null)q.offer(n.right);} if(sum>best){best=sum; bestLevel=level;} level++; } return bestLevel; } }复杂度
时间
O(n)
每个节点恰好出队、入队一次,累加时也只看一次,n 是节点数
空间
O(w)
w 是树的最大宽度,队列最坏要同时装下最宽一层(可达 n/2 量级)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大层内元素和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
用 DFS 能做吗?+
能。DFS 时多带一个深度参数 depth,维护一个数组 sums;每访问一个节点,就把它的值累加到 sums[depth] 上(depth 超出当前长度就先补一个 0)。整棵树走完后,在 sums 里找最大值对应的下标,加 1 就是层号(注意同样要处理并列时取最小下标)。前序遍历最自然。
这类「按层」的题还有哪些变体?+
把「求和」换成别的聚合就是一系列题:每层最大值、每层平均值、每层最右节点(右视图)、之字形层序、最小深度等。核心都是这套「队列按层展开」的 BFS 框架,只是每层做的聚合不同。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大层内元素和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。