# Share my O(logN+K) time , DFS and binary search in C++

• We maintain two arrays to track the larger and smaller number.
class Solution {

``````public:
//binary search, in order traversal, two arrays
//smaller array stores nearest numbers<target in descending order
//larger array stores nearest numbers>=target in ascending order
//O(logN+k);
void DFS(TreeNode *node, double target, int k,
vector<int> &larger, vector<int> &smaller){
if(!node)return;
if(target<=node->val){
DFS(node->left,target,k,larger,smaller);
larger.push_back(node->val);
if(larger.size()>=k)return; //Skip beacuse we only need nearest k numbers
DFS(node->right,target,k,larger,smaller);
}
else{
DFS(node->right,target,k,larger,smaller);
smaller.push_back(node->val);
if(smaller.size()>=k)return;//Skip beacuse we only need nearest k numbers
DFS(node->left,target,k,larger,smaller);
}
}
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> larger, smaller, ans;
DFS(root,target,k,larger,smaller);
int i=0,j=0;
//merge smaller array and larger array, get the nearest k numbers
while(ans.size()<k){
if(i==larger.size())ans.push_back(smaller[j++]);
else if(j==smaller.size())ans.push_back(larger[i++]);
else{
if(larger[i]-target<=target-smaller[j])ans.push_back(larger[i++]);
else ans.push_back(smaller[j++]);
}
}
return ans;
}
};``````

• I suspect your solution is not a O(K) solution. Since you are pushing nodes->val into array, and then merge together. Do you access all nodes in the tree? if so, your solution is O(n).

For a O(K) solution you must push TreeNode* into stack. that's the only way you can avoid visiting all nodes.

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