题目:
每层所有节点的和之中
第k大的和是多少
思路:
※ 引述 《DJYOMIYAHINA (通通打死)》
: 理论上好像应该BFS+size k的minheap
: 但我览
: 对不起
: 反正差不多
我哭了
又会刷题 人长的又帅
还会拿贴著Guardian 奖牌的鞭子
挥打我跟sustainer
好爱dj宝
我又晕船了...
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), ri
ght(right) {}
* };
*/
class Solution {
public:
long long kthLargestLevelSum(TreeNode* root, int k)
{
priority_queue<long long , vector<long long> , greater<long long> > pq;
queue<pair<long long,TreeNode*>> paper;
paper.push({0,root});
int curlayer = 0;
long long curval = 0;
while(!paper.empty())
{
auto now = paper.front();
paper.pop();
if(curlayer != now.first)
{
curlayer = now.first;
pq.push(curval);
curval = 0;
if(pq.size() > k)pq.pop();
}
curval += now.second->val;
if(now.second->left != NULL)paper.push({now.first+1,now.second->left
});
if(now.second->right != NULL)paper.push({now.first+1,now.second->rig
ht});
}
pq.push(curval);
if(pq.size() > k)pq.pop();
if(pq.size() < k)return -1;
return pq.top();
}
};
```