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

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
本站总访问量  次  |  您是本站第  位访问者