272. (Locked)Closest Binary Search Tree Value II

Difficulty: Hard

Frequency: N/A

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

  1. Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  2. Try to assume that each node has a parent pointer, it makes the problem much easier.
  3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  4. You would need two stacks to track the path in finding predecessor and successor node separately.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
    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;
    }
    void dfs(TreeNode* node, priority_queue<pair<double, int>>& pq, double target, int k) {
        if (!node) return;
        pq.push(make_pair(abs(target - (double)node->val), node->val));
        if (pq.size() > k) pq.pop();
        dfs(node->left, pq, target, k);
        dfs(node->right, pq, target, k);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s