2583.
※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: 理論上好像應該BFS+size k的minheap
真的欸
space差好多ㄛ==
原本想說反正全部都要加
1e5而已 就給他開下去
dfs比較好寫 對ㄚ
/**
* 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), right(right) {}
* };
*/
using ll = long long;
class Solution {
public:
vector<ll> lv_sum;
long long kthLargestLevelSum(TreeNode* root, int k) {
lv_sum = vector<ll>(1e5 + 7, 0);
int n = sum_up(0, root);
if(k > n) return -1;
lv_sum.resize(n);
ranges::sort(lv_sum);
return lv_sum[n-k];
}
int sum_up(int lv, TreeNode* cur){
if(cur == nullptr) return lv;
lv_sum[lv] += cur->val;
return max(sum_up(lv+1, cur->left), sum_up(lv+1, cur->right));
}
};