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.

Follow up:
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;
    }
};