Simple C++ solution with priority queue


  • 15
    J

    There are many ways to solve this problem. Heap is one of them.

    void dfs(TreeNode* root, priority_queue<pair<double, int>>& pq, double target, int k) {
        if(!root) return;
        
        pq.push(make_pair(fabs(target - double(root->val)), root->val));
        
        if(pq.size() > k) 
            pq.pop();
            
        dfs(root->left, pq, target, k);
        dfs(root->right, pq, target, k);
    }
    
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        priority_queue<pair<double, int>> pq;
        vector<int> result;
        
        dfs(root, pq, target, k);
        while(!pq.empty()) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        
        return result;
    }

  • 0

    Great code, very nice design of the pair<double, int> :-)


  • 0
    B

    Why are you popping front in these lines if(pq.size() > k) pq.pop();, will it no delete the closest value. as it will be at top of the pq?


  • 2
    H

    I think priority queue does not give less than O(n) time, since it visits all the node in the BST. To do it O(n) time, a simple in order traversal is more efficient. However, to achieve less than O(n) time we need to use the method following the hint.


  • 0
    Z

    What is the time complexity of this method? O(N) or O(NlogN)? Thanks


  • 0
    J

    It is O(nlogn). Slower than other solutions, but easy to make.


  • 1
    W

    O(nlogk), didn't know pair has a default comparator :)


  • 0
    H

    Code is pretty neat, yet it's O(Nlogk) which is worse than O(N) which can also be done with neat traverse code. However, it doesn't meet the better than O(N) request.


  • 0
    W

    @jaewoo Could you please tell me why the max-heap is used instead of min-heap? The problem seems to look for closest value, which means it is looking for k smallest difference between node value and target.


Log in to reply
 

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