Problem
Given the root of a binary tree, return the smallest level number that has the maximum sum of node values.The root is considered to be at level 1. For each level, calculate the sum of all node values at that level and return the level with the highest sum. If multiple levels have the same sum, return the smallest level number.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
root:
1
/ \
7 0
/ \ \
7 -8 7Output
2Example 2
Input
root:
989
/ \
10250 98693
/ \ \
100 -893 -321Output
2Solution
This solution uses Breadth-First Search (BFS) with a Queue to process the binary tree level by level.At the beginning of each level,
n stores the number of nodes currently in the queue. We process exactly those nodes and calculate their level sum using count. Their children are then added to the queue for the next level.
After processing each level, we compare its sum with the maximum sum found so far. If the current sum is greater, we update
max and store the current level in maxLevel.
class Solution {
public int maxLevelSum(TreeNode root) {
int max = Integer.MIN_VALUE;
int maxLevel = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
int n = queue.size();
level++;
int count = 0;
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
count += node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
if (count > max) {
max = count;
maxLevel = level;
}
}
return maxLevel;
}
}Complexity
Each node is processed exactly once, so the time complexity isO(n), where n is the number of nodes in the binary tree.
The queue stores nodes from the tree levels being processed. In the worst case, it can contain
O(n) nodes, so the extra space complexity is O(n).