熊二 | C++ | #第k轻的牛牛#

题目考查的知识点

• 堆排序
• 第k大/小的数
• 快速排序

题目解答方法的文字解析

1. 使用一个大小为k的大根堆来记录树的前k小的值
2. 堆弹出的元素 始终是没有位于前k小的
3. 使用中序遍历来遍历二叉树

本题解析所用的编程语言

• c++

完整且正确的编程代码

class Solution {
    int m_k;
public:
    priority_queue<int, vector<int>>pq;
    int kthLighest(TreeNode* root, int k) {
        m_k = k;
        traverse(root);
        return pq.top();
    }
    void traverse(TreeNode*node){
        if(!node)return;
        traverse(node->left);
        pq.push(node->val);
        if(pq.size()>m_k)pq.pop();
        traverse(node->right);
    }
};