Earliest Tree Level With the Largest Sum
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The root is at level 1 and each child is one level below its parent. Return the smallest level number whose node values have the maximum sum among all levels.
```cpp
class Solution {
public:
int maxLevelSum(TreeNode* root);
};
```
### Examples
**Example 1:**
```text
Input: root = [-2,-1,-1]
Output: 1
Explanation: Both levels sum to-2, so the smaller level number wins.
```
**Example 2:**
```text
Input: root = [1,3,5]
Output: 2
Explanation: Level2 sums to8, exceeding the root sum1.
```
### Constraints
- The tree contains 1 to 10000 nodes.
- Every node value is an integer in `[-100000,100000]`.
### Contract considerations
Preserve the native TreeNode input; the root level is 1, not 0.
```hint Read the boundary condition
If level sums tie or all are negative, which existing level must the result identify?
```
### Boundary reminders
Preserve the native TreeNode input; the root level is 1, not 0.
Overview: Earliest Tree Level With the Largest Sum. The root is at level1 and each child is one level below its parent.