272

272. Closest Binary Search Tree Value II (Hard)

Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.

You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

 

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

Example 2:

Input: root = [1], target = 0.000000, k = 1
Output: [1]

 

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 104.
• 0 <= Node.val <= 109
• -109 <= target <= 109

 

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

Companies: LinkedIn, Google, Amazon

Related Topics:
Two Pointers, Stack, Tree, Depth-First Search, Binary Search Tree, Heap (Priority Queue), Binary Tree

Similar Questions:

• Binary Tree Inorder Traversal (Easy)
• Closest Binary Search Tree Value (Easy)
• Closest Nodes Queries in a Binary Search Tree (Medium)

Solution 1. DFS + Heap

// OJ: https://leetcode.com/problems/closest-binary-search-tree-value-ii
// Author: github.com/lzl124631x
// Time: O(NlogK)
// Space: O(H + K)
class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        typedef pair<double, int> Node;
        auto cmp = [&](auto &a, auto &b) { return a.first < b.first; };
        priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
        function<void(TreeNode*)> dfs = [&](TreeNode *node) {
            if (!node) return;
            double d = abs(target - node->val);
            pq.emplace(d, node->val);
            if (pq.size() > k) pq.pop();
            dfs(node->left);
            dfs(node->right);
        };
        dfs(root);
        vector<int> ans;
        while (pq.size()) {
            ans.push_back(pq.top().second);
            pq.pop();
        }
        return ans;
    }
};