Re: [閒聊] 每日leetcode
題目:
每層所有節點的和之中
第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();
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.32.52 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729583043.A.D51.html
→
10/22 15:46,
1年前
, 1F
10/22 15:46, 1F
推
10/22 15:54,
1年前
, 2F
10/22 15:54, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 1022 之 1548 篇)：