跳至主要內容

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

ITCharge大约 2 分钟

0270. 最接近的二叉搜索树值open in new window

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

题目链接

题目大意

描述:给定一个不为空的二叉搜索树的根节点,以及一个目标值 targettarget

要求:在二叉搜索树中找到最接近目标值 targettarget 的数值。

说明

  • 树中节点的数目在范围 [1,104][1, 10^4] 内。
  • 0Node.val1090 \le Node.val \le 10^9
  • 109target109-10^9 \le target \le 10^9

示例

  • 示例 1:
输入:root = [4,2,5,1,3], target = 3.714286
输出:4
  • 示例 2:
输入:root = [1], target = 4.428571
输出:1

解题思路

思路 1:二分查找算法

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

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

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

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n),其中 nn 为二叉搜索树的节点个数。
  • 空间复杂度O(1)O(1)