📘 題目敘述
給你一棵二元樹的根節點 root。
第 i 層的總和定義為該層所有節點值的總和。
請回傳「節點值總和最大」的那一層的層數（層數從 1 開始）。
如果有多層的總和同樣最大，回傳層數最小的那一層。
條件限制
- 樹中節點數量在範圍
[1, 10^4] -10^5 <= Node.val <= 10^5
🧠 解題思路
我用 BFS 一層一層掃過去，因為題目要的就是「每一層的總和」。
所以我做的事情很固定：
- queue 裡面永遠放「下一個要處理的節點」
- 每一輪 while 就代表我要處理一層
- 我先記下這一層的節點數量
n = q.size()，確保接下來只處理這一層 - 把這一層的節點全部 pop 出來，累加它們的
val變成sum - 同時把下一層的節點 push 進 queue
處理完一層後，我把 sum 存進 nums，最後再掃一次 nums 找出最大值所在的層數。
這樣的好處是我把「算每層總和」跟「找最大的層」拆成兩段，邏輯很直覺。
所有變數
nums：每一層的總和，nums[i]代表第i+1層的總和q：BFS 用的 queue，存目前要處理的節點n：目前這一層的節點數量sum：目前這一層的總和ans：目前找到的最大層總和level：目前最大總和出現的層數（從 1 開始）
🪜 主要流程步驟
1. 用 BFS 一層一層計算總和
我把 root 放進 queue，然後開始 while。
每一輪 while：
n = q.size()代表這一層有幾個節點- 把這一層的
n個節點全部拿出來做加總 - 同時把它們的子節點丟進 queue，留給下一輪處理
2. 把每層的 sum 存進 nums
當一層的 for 迴圈跑完後，這層的 sum 就算完了。
我把它 push 進 nums，這樣 nums 就會依序存著：
第 1 層總和、第 2 層總和、第 3 層總和……
3. BFS 結束後，再掃一次 nums 找最大總和的層
我用 ans 記錄目前最大總和，用 level 記錄它出現在哪一層。
掃 nums 時：
- 如果
nums[j]比ans大 - 更新
ans - 更新
level = j + 1
因為我只在嚴格變大的時候更新，所以如果有相同最大值，會保留第一次出現的層數，也就符合「回傳層數最小」的要求。
⏱️ 複雜度
- 時間複雜度：
O(n)，每個節點只會被 push/pop 一次，加總也是一次。 - 空間複雜度：
O(n)，queue 最壞可能存一整層節點，另外nums也存了每層總和。
💻 程式碼實作
/**
* Definition for a binary tree node.
* 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) {
vector<int> nums;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
int sum = 0;
for (int i = 0; i < n; i++) {
TreeNode* node = q.front();
sum += node->val;
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
nums.push_back(sum);
}
int ans = INT_MIN;
int level = 0;
for (int j = 0; j < nums.size(); j++) {
if (ans < nums[j]) {
ans = nums[j];
level = j + 1;
}
}
return level;
}
};
🔗 題目連結
https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/