# 270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

Example:

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

4
/ \
2   5
/ \
1   3

Output: 4
``````

``````class Solution {
public:
int closestValue(TreeNode* root, double target) {
double d = numeric_limits<double>::max();
int res = 0;
stack<TreeNode*> s;
TreeNode *p = root;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
if (d >= abs(target - p->val)) {
d = abs(target - p->val);
res = p->val;
}
p = p->right;
}
return res;
}
};
``````

``````class Solution {
public:
int closestValue(TreeNode* root, double target) {
int res = root->val;
while (root) {
if (abs(res - target) >= abs(root->val - target)) {
res = root->val;
}
root = target < root->val ? root->left : root->right;
}
return res;
}
};
``````

``````class Solution {
public:
int closestValue(TreeNode* root, double target) {
int a = root->val;
TreeNode *t = target < a ? root->left : root->right;
if (!t) return a;
int b = closestValue(t, target);
return abs(a - target) < abs(b - target) ? a : b;
}
};
``````

``````class Solution {
public:
int closestValue(TreeNode* root, double target) {
int res = root->val;
if (target < root->val && root->left) {
int l = closestValue(root->left, target);
if (abs(res - target) >= abs(l - target)) res = l;
} else if (target > root->val && root->right) {
int r = closestValue(root->right, target);
if (abs(res - target) >= abs(r - target)) res = r;
}
return res;
}
};
``````

``````class Solution {
public:
int closestValue(TreeNode* root, double target) {
double diff = numeric_limits<double>::max();
int res = 0;
helper(root, target, diff, res);
return res;
}
void helper(TreeNode *root, double target, double &diff, int &res) {
if (!root) return;
if (diff >= abs(root->val - target)) {
diff = abs(root->val - target);
res = root->val;
}
helper(root->left, target, diff, res);
helper(root->right, target, diff, res);
}
};
``````

Github 同步地址：

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

Count Complete Tree Nodes

Closest Binary Search Tree Value II

Search in a Binary Search Tree

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

https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70331/Clean-and-concise-java-solution

https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70322/Super-clean-recursive-Java-solution

https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70327/4-7-lines-recursiveiterative-RubyC%2B%2BJavaPython

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

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

×

Help us with donation