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.


  • 0
    H

    This solution is suitable if the given input is a non-BST or any BT/array. Its complexity is O(N * logK). A more appropriate solution would leverage the benefits of BST while solving this problem.


Log in to reply
 

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