题目:
叫你对每个节点找出
全部同层的节点的值加起来
但是不包含同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();
}
};
```