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