Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目:
叫你對每個節點找出
全部同層的節點的值加起來
但是不包含同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();
    }
};
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.237.130 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729674497.A.5A8.html
→ deatheo: 大師