当前位置： 面试刷题>> 二叉搜索树中最接近的值 (经典算法题500道)
### 题目描述
给定一个非空二叉搜索树（BST）和一个目标值 `target`，找到BST中与目标值最接近的整数值。注意，BST中的每个节点都包含一个唯一的整数值。
**示例**:
假设BST如下：
```
4
/ \
2 5
/ \
1 3
```
对于目标值 `3.714286`，BST中与它最接近的整数值是 `4`。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function closestValue($root, $target) {
$closest = $root->val;
$diff = abs($root->val - $target);
while ($root !== null) {
$newDiff = abs($root->val - $target);
if ($newDiff < $diff) {
$diff = $newDiff;
$closest = $root->val;
}
if ($root->val === $target) {
break;
} elseif ($root->val < $target) {
$root = $root->right;
} else {
$root = $root->left;
}
}
return $closest;
}
// 示例用法
$root = new TreeNode(4);
$root->left = new TreeNode(2);
$root->right = new TreeNode(5);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(3);
$target = 3.714286;
echo closestValue($root, $target); // 输出 4
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def closestValue(root, target):
closest = root.val
diff = abs(root.val - target)
while root:
new_diff = abs(root.val - target)
if new_diff < diff:
diff = new_diff
closest = root.val
if root.val == target:
break
elif root.val < target:
root = root.right
else:
root = root.left
return closest
# 示例用法
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
target = 3.714286
print(closestValue(root, target)) # 输出 4
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function closestValue(root, target) {
let closest = root.val;
let diff = Math.abs(root.val - target);
while (root) {
let newDiff = Math.abs(root.val - target);
if (newDiff < diff) {
diff = newDiff;
closest = root.val;
}
if (root.val === target) {
break;
} else if (root.val < target) {
root = root.right;
} else {
root = root.left;
}
}
return closest;
}
// 示例用法
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
const target = 3.714286;
console.log(closestValue(root, target)); // 输出 4
```
**码小课**：在算法和数据结构的学习中，理解和实现二叉搜索树（BST）的相关操作是非常重要的。通过不断练习和解决实际问题，可以加深对BST特性的理解。码小课网站上有更多关于BST和其他算法的数据结构与算法相关内容，欢迎大家前往学习。