1161. Maximum Level Sum of a Binary Tree
1. Description
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.
2. Example
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
3. Constraints
- The number of nodes in the tree is in the range [1, $10^4$].
- -$10^5$ <= Node.val <= $10^5$
4. Solutions
Breadth-First Search
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int maxLevelSum(TreeNode *root) {
int level = 1, max_sum_level = 1, max_sum = root->val;
queue<TreeNode *> level_nodes{{root}};
while (!level_nodes.empty()) {
int sum = 0;
int node_count = level_nodes.size();
for (int i = 0; i < node_count; ++i) {
auto node = level_nodes.front();
level_nodes.pop();
if (node->left != nullptr) {
level_nodes.push(node->left);
}
if (node->right != nullptr) {
level_nodes.push(node->right);
}
sum += node->val;
}
if (sum > max_sum) {
max_sum = sum;
max_sum_level = level;
}
++level;
}
return max_sum_level;
}
};