Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
997 B
0
Indexable
Never
#define ll long long
class Solution {
public:
    struct cmp{
        bool operator() (const pair<TreeNode*,ll>&a, const pair<TreeNode*,ll>&b){
            return a.second < b.second;
        }
    };

    long long kthLargestLevelSum(TreeNode* root, int k) {
        priority_queue<pair<TreeNode*,ll>,vector<pair<TreeNode*,ll>>, cmp> pq; //node,level
        vector<ll>levelsum(100000);
        pq.push({root,0});
        ll totlevl=0;
        while(!pq.empty()){
            pair<TreeNode*,ll> top = pq.top();
            pq.pop();
            TreeNode* node = top.first;
            ll lev = top.second;
            levelsum[lev] += node->val;
            totlevl=max(totlevl,lev+1);
            if(node->left) pq.push({node->left, lev+1});
            if(node->right) pq.push({node->right, lev+1});
            
        }

        sort(levelsum.begin(), levelsum.end(), greater<ll>());
        cout<<totlevl;
        return totlevl>=k?levelsum[k-1]:-1;
    }
};
Leave a Comment