Article / 文章
LeetCode 第270题：最接近的二叉搜索树值
给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。 注意： - 给定的目标值 target 是一个浮点数 - 题目保证在该二叉搜索树中只会存在一个最接近目标值的数
📖 文章摘要
本文详细解析LeetCode第270题“最接近的二叉搜索树值”，这是一道二叉搜索树的简单问题。文章提供了从基础遍历到高效BST特性利用的多种解法，包含递归和迭代两种实现方式，配有详细的BST搜索过程图解和距离计算分析。适合想要掌握二叉搜索树基础操作和优化技巧的算法学习者。
核心知识点： 二叉搜索树、递归遍历、迭代搜索、距离计算
难度等级： 简单
推荐人群： 二叉搜索树初学者、树结构算法爱好者
题目描述
给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。
注意：
- 给定的目标值
target是一个浮点数 - 题目保证在该二叉搜索树中只会存在一个最接近目标值的数
示例
示例 1：
输入: root = [4,2,5,1,3], target = 3.714286
4
/ \
2 5
/ \
1 3
输出: 4示例 2：
输入: root = [1], target = 4.428571
输出: 1提示
- 树中节点数目在范围
[1, 10^4]内 0 <= Node.val <= 10^9-10^9 <= target <= 10^9
解题思路
这道题要求在二叉搜索树中找到最接近目标值的节点值。可以利用二叉搜索树的性质来优化搜索过程。
核心分析
二叉搜索树特性：
- 左子树所有节点值 < 根节点值 < 右子树所有节点值
- 可以通过比较大小确定搜索方向
- 不需要遍历所有节点，只需沿着一条路径搜索
解题策略：
- 利用BST性质，根据目标值与当前节点值的大小关系选择搜索方向
- 在搜索过程中维护当前找到的最接近值
- 比较距离时使用绝对值计算
方法一：递归法
核心思想：
- 利用二叉搜索树的性质，根据目标值与当前节点值的大小关系来决定搜索方向
- 递归比较当前节点值与子树中找到的最接近值
- 返回距离目标值更近的那个值
具体步骤：
- 获取当前节点的值
- 根据目标值与当前节点值的大小关系，选择搜索左子树或右子树
- 如果子树为空，返回当前节点值
- 递归搜索子树，获得子树中最接近的值
- 比较当前节点值和子树最接近值与目标值的距离，返回更接近的那个
复杂度分析：
- 时间复杂度：O(H)，其中H是树的高度
- 空间复杂度：O(H)，递归调用栈的深度
方法二：迭代法
核心思想：
- 使用迭代的方式遍历二叉搜索树
- 在遍历过程中维护最接近的值
- 利用BST性质确定搜索方向
具体步骤：
- 初始化最接近值为根节点值
- 从根节点开始遍历
- 比较当前节点值与目标值的距离，更新最接近值
- 根据目标值与当前节点值的大小关系，选择下一个搜索方向
- 重复直到遍历完成
复杂度分析：
- 时间复杂度：O(H)，其中H是树的高度
- 空间复杂度：O(1)
图解思路
算法步骤分析表
| 步骤 | 当前节点 | 目标值 | 距离计算 | 最接近值 | 下一步方向 | 说明 |
|---|---|---|---|---|---|---|
| 初始状态 | 4 | 3.714286 | 4-3.714286 | =0.285714 | 4 | |
| 第一步 | 2 | 3.714286 | 2-3.714286 | =1.714286 | 4 | |
| 第二步 | 3 | 3.714286 | 3-3.714286 | =0.714286 | 4 | |
| 结果 | - | - | - | 4 | - | 返回距离最小的节点值 |
距离比较分析表
| 节点值 | 与目标值距离 | 是否更新最接近值 | 说明 |
|---|---|---|---|
| 4 | 4-3.714286 | =0.285714 | |
| 2 | 2-3.714286 | =1.714286 | |
| 3 | 3-3.714286 | =0.714286 | |
| 1 | 1-3.714286 | =2.714286 | |
| 5 | 5-3.714286 | =1.285714 |
代码实现
C# 实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
// 方法一：递归法（推荐）
public class Solution {
public int ClosestValue(TreeNode root, double target) {
int val = root.val;
TreeNode child = target < val ? root.left : root.right; // 根据目标值选择搜索方向
if (child == null) return val; // 如果子树为空，返回当前节点值
int childClosest = ClosestValue(child, target); // 递归搜索子树
return Math.Abs(val - target) < Math.Abs(childClosest - target) ? val : childClosest; // 返回更接近的值
}
}
// 方法二：迭代法
public class Solution {
public int ClosestValue(TreeNode root, double target) {
int closest = root.val; // 初始化最接近值
while (root != null) {
if (Math.Abs(root.val - target) < Math.Abs(closest - target)) {
closest = root.val; // 更新最接近值
}
root = target < root.val ? root.left : root.right; // 选择搜索方向
}
return closest;
}
}Python 实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 方法一：递归法（推荐）
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
val = root.val
child = root.left if target < val else root.right # 根据目标值选择搜索方向
if not child:
return val # 如果子树为空，返回当前节点值
child_closest = self.closestValue(child, target) # 递归搜索子树
return val if abs(val - target) < abs(child_closest - target) else child_closest # 返回更接近的值
# 方法二：迭代法
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
closest = root.val # 初始化最接近值
while root:
if abs(root.val - target) < abs(closest - target):
closest = root.val # 更新最接近值
root = root.left if target < root.val else root.right # 选择搜索方向
return closestC++ 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// 方法一：递归法（推荐）
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int val = root->val;
TreeNode* child = target < val ? root->left : root->right; // 根据目标值选择搜索方向
if (!child) return val; // 如果子树为空，返回当前节点值
int childClosest = closestValue(child, target); // 递归搜索子树
return abs(val - target) < abs(childClosest - target) ? val : childClosest; // 返回更接近的值
}
};
// 方法二：迭代法
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int closest = root->val; // 初始化最接近值
while (root) {
if (abs(root->val - target) < abs(closest - target)) {
closest = root->val; // 更新最接近值
}
root = target < root->val ? root->left : root->right; // 选择搜索方向
}
return closest;
}
};执行结果
C# 实现
- 递归法：执行用时：88 ms，内存消耗：41.2 MB
- 迭代法：执行用时：84 ms，内存消耗：40.8 MB
Python 实现
- 递归法：执行用时：44 ms，内存消耗：16.8 MB
- 迭代法：执行用时：40 ms，内存消耗：16.5 MB
C++ 实现
- 递归法：执行用时：12 ms，内存消耗：21.3 MB
- 迭代法：执行用时：8 ms，内存消耗：21.1 MB
性能对比
| 语言 | 方法 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|---|
| C++ | 迭代法 | 8 ms | 21.1 MB | 性能最优，空间效率最高 |
| C++ | 递归法 | 12 ms | 21.3 MB | 性能优秀，代码简洁 |
| Python | 迭代法 | 40 ms | 16.5 MB | 内存占用最小 |
| C# | 迭代法 | 84 ms | 40.8 MB | 性能良好，逻辑清晰 |
代码亮点
- 🎯 充分利用二叉搜索树的性质，将时间复杂度从O(N)优化到O(H)
- 💡 提供递归和迭代两种实现方式，迭代法在空间复杂度上更优
- 🔍 正确处理浮点数比较，使用绝对值计算距离
- 🎨 代码结构清晰，逻辑简洁，易于理解和维护
常见错误分析
- 🚫 没有充分利用BST性质，使用了O(N)的遍历方法
- 🚫 浮点数比较时没有考虑精度问题，直接使用等号比较
- 🚫 递归实现时没有正确处理空节点的边界情况
- 🚫 忘记比较当前节点与子树结果，直接返回子树结果
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 递归法 | O(H) | O(H) | 代码简洁，思路清晰 | 需要递归调用栈空间 |
| 迭代法 | O(H) | O(1) | 空间复杂度最优 | 代码稍微复杂一些 |
| 中序遍历 | O(N) | O(N) | 思路直观 | 没有利用BST性质，效率低 |
相关题目
- LeetCode 272. 最接近的二叉搜索树值 II - 困难
- LeetCode 700. 二叉搜索树中的搜索 - 简单
- LeetCode 701. 二叉搜索树中的插入操作 - 中等
- LeetCode 450. 删除二叉搜索树中的节点 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第270题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！