0270. 最接近的二叉搜索树值 #

• 标签：树、深度优先搜索、二叉搜索树、二分查找、二叉树
• 难度：简单

题目大意 #

给定一个不为空的二叉搜索树，以及一个目标值 target。要求在二叉搜索树中找到最接近目标值 target 的数值。

解题思路 #

题目中最接近目标值 target 的数值指的就是 与 target 相减绝对值最小的数值。

而且根据二叉搜索树的性质，我们可以利用二分搜索的方式，查找与 target 相减绝对值最小的数值。具体做法为：

• 定义一个变量 closest 表示与 target 最接近的数值，初始赋值为根节点的值 root.val。
• 判断当前节点的值域 closet 值哪个更接近 target，如果当前值更接近，则更新 closest。
• 如果 target < 当前节点值，则从当前节点的左子树继续查找。
• 如果 target ≥ 当前节点值，则从当前节点的右子树继续查找。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = root.val
        while root:
            if abs(target - root.val) < abs(target - closest):
                closest = root.val
            if target < root.val:
                root = root.left
            else:
                root = root.right
        return closest