1161. Maximum Level Sum of a Binary Tree

2026, Jan 27 2 mins read

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

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
    }
};