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.

&nbsp;
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


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 104].
	-105 &lt;= Node.val &lt;= 105


 class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        global_max = float('-inf')
        res = -1
        q = deque([root])
        lvl = 1
        while q:
            total = 0
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                total+=node.val
            if total>global_max:
                res = lvl
                global_max = total
            lvl+=1
        return res
class Solution {
    Map<Integer, Integer> map = new HashMap<>();

    public void go(TreeNode root, int level) {
        if(root == null) return;
        if(map.containsKey(level)) {
            map.put(level, map.get(level) + root.val);
        }
        else {
            map.put(level, root.val);
        }

        go(root.left, level+1);
        go(root.right, level+1);
    }
    public int maxLevelSum(TreeNode root) {
        go(root, 0);
        int max = Integer.MIN_VALUE, ind = -1;
        for (var i : map.entrySet()) {
            if(max < i.getValue()) {
                max = i.getValue();
                ind = i.getKey();
            }
        }
        return ind+1;
    }
}
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        int maxSum = INT_MIN;
        int minLevel = 1;
        
        int level = 1;
        queue<TreeNode*> qq;
        qq.push(root);
		// level order traversal
        while(!qq.empty()){
            int size = qq.size();
            int currSum  = 0;
            while(size--){
                auto node = qq.front();
                qq.pop();
                currSum += node->val;
                if(node->left)qq.push(node->left);
                if(node->right)qq.push(node->right);
            }
            if(currSum>maxSum){
                maxSum = currSum;
                minLevel = level;
            }
            level++;
        }
        
        return minLevel;
    }
};
var maxLevelSum = function(root) {
    let res;
    let maxSum = -Infinity;
    let currLevel = 1;

    const queue = [root];

    while (queue.length) {
        let levelSize = queue.length;
        let levelSum = 0;

        for (let i = 0; i < levelSize; i++) {
            let curr = queue.shift();
            levelSum += curr.val;

            if (curr.left) queue.push(curr.left);
            if (curr.right) queue.push(curr.right);
        }

        if (maxSum < levelSum) {
            res = currLevel;
            maxSum = levelSum
        }

        currLevel++;
    }

    return res;
};
Maximum Level Sum of a Binary Tree