Maximum Level Sum of a Binary Tree
題目描述
給定一棵二元樹的根節點 root，回傳節點值總和最大的層級編號（根為第 1 層）。如果有多個層級總和相同，回傳最小的層級編號。
輸入: 1
/ \
7 0
/ \
7 -8
輸出: 2
解釋: 第 1 層和 = 1，第 2 層和 = 7+0=7，第 3 層和 = 7+(-8)=-1
最大的是第 2 層。
解題思路
BFS 初始化
將 root 放入 Queue，設 level = 0、maxSum = 負無限大、resultLevel = 1
逐層處理
level++ 後用 levelSize 控制內層迴圈，累加所有出隊節點的值得到 levelSum
比較更新
若 levelSum 嚴格大於 maxSum，更新 maxSum 和 resultLevel（用嚴格大於確保取最小層級）
進入下一層
內層迴圈中已將下一層子節點加入 Queue，外層繼續處理直到 Queue 為空
程式碼
C#
public class Solution {
public int MaxLevelSum(TreeNode root) {
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
int maxSum = int.MinValue;
int resultLevel = 1;
int level = 0;
while (queue.Count > 0) {
level++;
int levelSize = queue.Count;
int levelSum = 0;
for (int i = 0; i < levelSize; i++) {
var node = queue.Dequeue();
levelSum += node.val;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
if (levelSum > maxSum) {
maxSum = levelSum;
resultLevel = level;
}
}
return resultLevel;
}
}TypeScript
function maxLevelSum(root: TreeNode | null): number {
const queue: TreeNode[] = [root!];
let maxSum = -Infinity;
let resultLevel = 1;
let level = 0;
while (queue.length > 0) {
level++;
const levelSize = queue.length;
let levelSum = 0;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
levelSum += node.val;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
if (levelSum > maxSum) {
maxSum = levelSum;
resultLevel = level;
}
}
return resultLevel;
}Python
from collections import deque
def maxLevelSum(root: Optional[TreeNode]) -> int:
queue = deque([root])
max_sum = float('-inf')
result_level = 1
level = 0
while queue:
level += 1
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level_sum > max_sum:
max_sum = level_sum
result_level = level
return result_level複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(w) |
w 是樹的最大寬度。Time O(n) 是因為每個節點入隊出隊各一次、做一次加法。Space O(w) 是 Queue 同時存放一層節點，完全二元樹最大寬度約 n/2。
邊界情況
- 只有根節點：只有第 1 層，直接回傳 1
- 所有層總和為負數：初始化 maxSum 為負無限大，確保負數也能正確比較
- 多層總和相同：使用嚴格大於（
>）而非大於等於（>=），自動保留最小的層級編號
圖解
圖表展示了三層的計算過程：Level 1 總和 1、Level 2 總和 7（最大）、Level 3 總和 -1。Level 2 的 7 嚴格大於其他層，所以答案為 Level 2。
進階觀點
💡面試追問
Q: DFS 能解這題嗎？
A: 可以。用 DFS 遍歷時記錄 depth，用 HashMap 或 Array（levelSums[depth] += node.val）累加每層總和。遍歷完後找最大值的 index。BFS 更直覺因為天然按層處理，不需額外資料結構。
Q: 為什麼 maxSum 要初始化為負無限大而不是 0？ A: 節點值可能是負數（題目明確說明）。如果所有層的總和都是負數，初始化為 0 會導致永遠不更新 resultLevel，回傳錯誤結果。
變體題：LC 515 Find Largest Value in Each Tree Row（每層最大值）、LC 637 Average of Levels（每層平均值）。
理解測驗
🤔 如果第 2 層和第 4 層的總和都是最大值，應該回傳哪一層？
🤔 為什麼要用 levelSize 控制內層迴圈，而不是直接處理到 Queue 為空？