# [LeetCode] 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.

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);
}
};

|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构

35 4
|
1月前
|
Python
【Leetcode刷题Python】538. 把二叉搜索树转换为累加树
LeetCode上538号问题"把二叉搜索树转换为累加树"的Python实现，使用反向中序遍历并记录节点值之和来更新每个节点的新值。
17 3
|
3月前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
34 0
|
3月前
|

LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
24 0
|
3月前
|

python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
35 0
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III

41 6
|
1月前
|

【Leetcode刷题Python】牛客. 数组中未出现的最小正整数

71 2
|
1月前
|

【Leetcode刷题Python】从列表list中创建一颗二叉树

35 7
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈

17 4
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案，使用双指针法找到并返回链表中倒数第k个节点。
40 5