题目描述
思路解析动画文字版
记住「队列按层展开,每层求和、和更大才换最佳层号」,下面逐帧套它。
什么是层：先找感觉:同一深度的节点属于同一层。根 1 是第 1 层,孩子 7、0 是第 2 层,再往下 7、-8 是第 3 层。我们要算每一层的和,挑和最大的那一层。
第 1 层就位：进入第 1 层,队列里是 [1]。先把这一整层从左到右扫一遍,边扫边把值累加成本层的和。
第 1 层 · 累加：从队首取出 1(红色高亮),把它加进本层的和:0 加 1 得到 1。
第 1 层 · 收孩子：1 加完了。把它的非空孩子 7、0(蓝色)加入下一层,目前下一层攒到了 [7、0]。
第 1 层和 = 1：第 1 层扫完,本层和是 1。它是第一层,直接成为目前的最大层和,最佳层号记为第 1 层。
第 2 层就位：进入第 2 层,队列里是 [7、0]。先把这一整层从左到右扫一遍,边扫边把值累加成本层的和。
第 2 层 · 累加：从队首取出 7(红色高亮),把它加进本层的和:0 加 7 得到 7。
第 2 层 · 收孩子：7 加完了。把它的非空孩子 7、-8(蓝色)加入下一层,目前下一层攒到了 [7、-8]。
第 2 层 · 累加：从队首取出 0(红色高亮),把它加进本层的和:7 加 0 得到 7。
第 2 层 · 收孩子：0 是叶子,没有孩子可加,下一层暂时还是 [7、-8]。
第 2 层和 = 7：第 2 层扫完,本层和是 7。7 比之前的最大 1 更大,最佳层号更新成第 2 层。
第 3 层就位：进入第 3 层,队列里是 [7、-8]。先把这一整层从左到右扫一遍,边扫边把值累加成本层的和。
第 3 层 · 累加：从队首取出 7(红色高亮),把它加进本层的和:0 加 7 得到 7。
第 3 层 · 收孩子：7 是叶子,没有孩子可加,下一层暂时还是 [空]。
第 3 层 · 累加：从队首取出 -8(红色高亮),把它加进本层的和:7 加上负数 -8 得到 -1。
第 3 层 · 收孩子：-8 是叶子,没有孩子可加,下一层暂时还是 [空]。
第 3 层和 = -1：第 3 层扫完,本层和是 -1。-1 没有超过之前的最大 7(在第 2 层),最佳层号保持第 2 层不变。 队列已空,BFS 即将结束。
完成：三层的和依次是 1、7、-1,最大的是 7,出现在第 2 层,所以答案是 2(金色标出这一层)。回头看,就是一遍标准的按层 BFS,每层求和、和更大才换最佳层号,一次遍历就出答案,时间 O(n)。
边界:单节点返回 1、负数层靠负无穷起步、并列取最小层号。
两个追问:DFS 带 depth 往 sums[depth] 累加也能做;按层 BFS 框架解一大类题。
参考代码
from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass 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_level复杂度
- 时间：O(n)，每个节点恰好出队、入队一次,累加时也只看一次,n 是节点数
- 空间：O(w)，w 是树的最大宽度,队列最坏要同时装下最宽一层(可达 n/2 量级)
易错点
面试追问把动画讲成自己的话
追问用 DFS 能做吗?
追问这类「按层」的题还有哪些变体?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
层数最深叶子节点的和
LeetCode 1302 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题