# O(n) Solution

• ...
/**

• 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:

TreeNode* getPredecessor(TreeNode* node, stack<TreeNode*>& Pre)
{
if(node&&node->left)
{
node = node->left;
while(node&&node->right!=nullptr){ Pre.push(node); node=node->right; }
return node;
}
else
{
node = nullptr;
if(Pre.size()) {node = Pre.top(); Pre.pop();}
return node;
}
}

TreeNode* getSuccessor(TreeNode* node, stack<TreeNode*>& Suc)
{
if(node&&node->right)
{
node = node->right;
while(node&&node->left!=nullptr){ Suc.push(node); node=node->left;}
return node;
}
else
{
node = nullptr;
if(Suc.size()){node = Suc.top(); Suc.pop();}
return node;
}
}

vector<int> closestKValues(TreeNode* root, double target, int k) {

`````` vector<int> result;
if(root==nullptr||k==0)
return result;

stack<TreeNode*> Pre;
stack<TreeNode*> Suc;
TreeNode *node = root;

while(node!=nullptr)
{
if(node->val<=target){Pre.push(node); node = node->right;}
else if(node->val>target){Suc.push(node);node = node->left;}
}
TreeNode* pre =  getPredecessor(nullptr,Pre);
TreeNode* suc =  getSuccessor(nullptr,Suc);
while(result.size()<k)
{
if(pre&&suc)
{
if( target - pre->val >= suc->val - target ){  result.push_back(suc->val); suc = getSuccessor(suc,Suc); }
else{ result.push_back(pre->val); pre = getPredecessor(pre,Pre); }
}
else if(suc==nullptr)   {  result.push_back(pre->val); pre = getPredecessor(pre,Pre);}
else                    {  result.push_back(suc->val); suc = getSuccessor(suc,Suc);}
}
return result;
``````

}
};
...

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