# [leetcode] Closest Binary Search Tree Value II

Closest Binary Search Tree Value II

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.

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

convert it to sequence, then find it.

```//convert the tree to a sequence
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> tree;
convert(root, tree);
int index = binarySearch(tree, target);//find the closest value, return its index
vector<int> ans = findK(tree, index, k, target);
return ans;
}
void convert(TreeNode * root, vector<int>& tree){
//inorder traversal
if(root == nullptr){
return ;
}
convert(root->left, tree);
tree.push_back(root->val);
convert(root->right, tree);
}
int binarySearch(vector<int>& tree, double target){
int start = 0;
int end = tree.size() - 1;
if(start == end) return start;
while(end - start > 1){
int mid = (start + end) / 2;
if(tree[mid] < target){
start = mid;
}
else{
end = mid;
}
}
int index = abs(target - tree[start]) < abs(target - tree[end])? start: end;
return index;
}
vector<int> findK(vector<int> tree, int index, int k, int target){
vector<int> ans;
ans.push_back(tree[index]);
k--;
int candidate1 = index - 1;
int candidate2 = index + 1;
while(k > 0){
int candidate;
if(candidate1 >= 0 && candidate2 < tree.size()){
candidate = abs(tree[candidate1] - target) < abs(tree[candidate2] - target)? candidate1--: candidate2++;
}
else if(candidate1 >= 0){
candidate = candidate1--;
}
else{
candidate = candidate2++;
}
ans.push_back(tree[candidate]);
k--;
}
return ans;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.