# 1161. Maximum Level Sum of a Binary Tree

Given the `root` of a binary tree, the level of its root is `1`, the level of its children is `2`, and so on.

Return the smallest level `x` such that the sum of all the values of nodes at level `x` is maximal.

Example 1:

``````Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.
``````

Example 2:

``````Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 104]`.
• `-105 <= Node.val <= 105`

Binary Tree Level Order Traversal II，做过这两道的话，这道题也就没啥难度了。这里还是用 queue 来辅助遍历，先将根结点放入队列，然后开始 while 循环遍历，先将初始化为0的 level 自增1，因为根结点是层数1。因为当前 queue 里的所有结点都属于同一层，需要一起遍历完，为了防止后来新加入 queue 的结点污染，这里用个 for 循环遍历当前层的所有结点，注意 q.size() 必须放在初始化里，而不能是判断条件里，因为其会改变，累加每层所有的结点值之和到 sum，然后跟全局的 mx 对比，若 sum 大于 mx，则更新 sum 为 mx，同时更新 res 为当前层数，参见代码如下：

``````class Solution {
public:
int maxLevelSum(TreeNode* root) {
int res = 1, mx = root->val, level = 0;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
++level;
int sum = 0;
for (int i = q.size(); i > 0; --i) {
TreeNode* t = q.front(); q.pop();
sum += t->val;
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
if (mx < sum) {
mx = sum;
res = level;
}
}
return res;
}
};
``````

``````class Solution {
public:
int maxLevelSum(TreeNode* root) {
vector<int> sums;
helper(root, 1, sums);
return distance(begin(sums), max_element(begin(sums), end(sums))) + 1;
}
void helper(TreeNode* node, int level, vector<int>& sums) {
if (!node) return;
if (sums.size() < level) sums.resize(level);
sums[level - 1] += node->val;
helper(node->left, level + 1, sums);
helper(node->right, level + 1, sums);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1161

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal II

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/discuss/360968/JavaPython-3-Two-codes-language%3A-BFS-level-traversal-and-DFS-level-sum.

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/discuss/360973/C%2B%2B-track-level-sum

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation