Re: [閒聊] 每日leetcode

[sixB (6B)]

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
→ DJYOMIYAHINA: 別卷了
推 steven183: 別卷了