class Solution {
public:
    typedef long long ll;
    
    int maxLevelSum(TreeNode* root) {
        vector<int> levels(1e5, 0);
        queue<pair<int,TreeNode*>> q;
        if(!root)
            return 0;
        q.push({0, root});
        int lvls_reached = 0;
        while(!q.empty()){
            auto node(q.front().second);auto lvl(q.front().first);
            q.pop();
            levels[lvl] += node->val;
            lvls_reached = max(lvls_reached, lvl);
            if(node->left)
                q.push({lvl + 1, node->left});
            if(node->right)
                q.push({lvl + 1, node->right});
        }
        ll maxi = LLONG_MIN;
        int ans = -1;
        for(int i = 0; i <=lvls_reached; i++)
            if(levels[i] > maxi)
                ans = i, maxi = levels[i];
        return ans + 1;
    }
};