900. Closest Binary Search Tree

Description

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Given target value is a floating point.

You are guaranteed to have only one unique value in the BST that is closest to the target.

Example

Example1

Input: root = {5,4,9,2,#,8,10} and target = 6.124780

Output: 5

Explanation：

Binary tree {5,4,9,2,#,8,10},  denote the following structure:

        5

      / \

    4    9

    /    / \

  2    8  10

Example2

Input: root = {3,2,4,1} and target = 4.142857

Output: 4

Explanation：

Binary tree {3,2,4,1},  denote the following structure:

    3

    / \

  2    4

/

1

思路：

核心想法是先找出最接近target的上下两个值， 然后取与target差值绝对值最小的一个，返回， 答案有用递归和不递归的两种方法， 然后我自己用传参数的方法也写了一堆可以通过的。

求出 lowerBound 和 upperBound。即 < target 的最大值和 >= target 的最小值。然后在两者之中去比较谁更接近，然后返回即可。这种方法的时间复杂度为 O(h)，注意如果你使用 in-order traversal 的化，时间复杂度会是 o(n)o(n) 并不是最优的。另外复杂度也不是 O(logn)O(logn) 因为BST 并不保证树高是 logn 的。

代码：

不用递归的：

我自己写的