872. Find Maximum Level Sum in Binary Tree

Given the root of a binary tree, return the 1-indexed level (the root is level 1) whose node values have the greatest sum. If multiple levels tie, return the smallest such level number. An empty tree returns 0. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Integer — the level with the maximum sum.

Examples

Input: [1,7,0,7,-8]
Output: 2
Explanation: Level 2 sums to 7, the maximum.

Input: [1]
Output: 1
Explanation: Only one level.

Input: [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
Explanation: Level 2 has the larger sum.

Constraints

• 1<=nodes<=10^4
• -10^5<=value<=10^5

Asked by