# 272. 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.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and _k_ = 2

4
/ \
2   5
/ \
1   3

Output: [4,3]

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

class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res, v;
inorder(root, v);
int idx = 0;
double diff = numeric_limits<double>::max();
for (int i = 0; i < v.size(); ++i) {
if (diff >= abs(target - v[i])) {
diff = abs(target - v[i]);
idx = i;
}
}
int left = idx - 1, right = idx + 1;
for (int i = 0; i < k; ++i) {
res.push_back(v[idx]);
if (left >= 0 && right < v.size()) {
if (abs(v[left] - target) > abs(v[right] - target)) {
idx = right;
++right;
} else {
idx = left;
--left;
}
} else if (left >= 0) {
idx = left;
--left;
} else if (right < v.size()) {
idx = right;
++right;
}
}
return res;
}
void inorder(TreeNode *root, vector<int> &v) {
if (!root) return;
inorder(root->left, v);
v.push_back(root->val);
inorder(root->right, v);
}
};

class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res;
inorder(root, target, k, res);
return res;
}
void inorder(TreeNode *root, double target, int k, vector<int> &res) {
if (!root) return;
inorder(root->left, target, k, res);
if (res.size() < k) res.push_back(root->val);
else if (abs(root->val - target) < abs(res[0] - target)) {
res.erase(res.begin());
res.push_back(root->val);
} else return;
inorder(root->right, target, k, res);
}
};

class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
if (res.size() < k) res.push_back(p->val);
else if (abs(p->val - target) < abs(res[0] - target)) {
res.erase(res.begin());
res.push_back(p->val);
} else break;
p = p->right;
}
return res;
}
};

class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res;
priority_queue<pair<double, int>> q;
inorder(root, target, k, q);
while (!q.empty()) {
res.push_back(q.top().second);
q.pop();
}
return res;
}
void inorder(TreeNode *root, double target, int k, priority_queue<pair<double, int>> &q) {
if (!root) return;
inorder(root->left, target, k, q);
q.push({abs(root->val - target), root->val});
if (q.size() > k) q.pop();
inorder(root->right, target, k, q);
}
};

class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res;
stack<TreeNode*> pre, suc;
while (root) {
if (root->val <= target) {
pre.push(root);
root = root->right;
} else {
suc.push(root);
root = root->left;
}
}
while (k-- > 0) {
if (suc.empty() || !pre.empty() && target - pre.top()->val < suc.top()->val - target) {
res.push_back(pre.top()->val);
getPredecessor(pre);
} else {
res.push_back(suc.top()->val);
getSuccessor(suc);
}
}
return res;
}
void getPredecessor(stack<TreeNode*> &pre) {
TreeNode *t = pre.top(); pre.pop();
if (t->left) {
pre.push(t->left);
while (pre.top()->right) pre.push(pre.top()->right);
}
}
void getSuccessor(stack<TreeNode*> &suc) {
TreeNode *t = suc.top(); suc.pop();
if (t->right) {
suc.push(t->right);
while (suc.top()->left) suc.push(suc.top()->left);
}
}
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/272

Closest Binary Search Tree Value

Binary Tree Inorder Traversal

https://leetcode.com/problems/closest-binary-search-tree-value-ii/

https://leetcode.com/problems/closest-binary-search-tree-value-ii/discuss/70515/Java-in-order-traversal-1ms-solution

https://leetcode.com/problems/closest-binary-search-tree-value-ii/discuss/70511/AC-clean-Java-solution-using-two-stacks

https://leetcode.com/problems/closest-binary-search-tree-value-ii/discuss/70503/O(logN)-Java-Solution-with-two-stacks-following-hint

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation