Closest Binary Search Tree Value II


  • 0
    A

    I saw a number of posts using two stacks. One alternative is to use a min heap. Running time: O(n + k*log(n)).

    // To compare two points
    class myComparator
    {
    public:
        int operator() (const pair<double,int>& p1, const pair<double,int>& p2)
        {
            return p1.first > p2.first;
        }
    };
    
    using MinHeap = priority_queue<pair<double,int>, vector<pair<double,int>>, myComparator>;
    class Solution {
    public:
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            MinHeap minHeap;
            makeHeap(root, minHeap, target);
            
            vector<int> closestVals;
            while (k-- > 0) {
                auto pairVal = minHeap.top();
                minHeap.pop();
                closestVals.push_back(pairVal.second);
            }
            
            return closestVals;
        }
        
    private:
        void makeHeap(TreeNode* root, MinHeap& minHeap, double target) {
            if (root != nullptr) {
                minHeap.push(make_pair(abs(target-root->val), root->val));
                makeHeap(root->left, minHeap, target);
                makeHeap(root->right, minHeap, target);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.