題目:
叫你對每個節點找出
全部同層的節點的值加起來
但是不包含同parent 的節點的值
思路:
遍歷兩次
一次紀錄層數的值
一次紀錄同個parent的值
用bfs是因為原本想試試看只遍歷一次
然後同時更新節點
後來想了想
發現這樣不太可能
因為沒有辦法把同層節點跑完之後再回去更改
一定是要兩次
姆咪
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();
}
};
```