901. Closest Binary Search Tree

Description

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

Given target value is a floating point.

You may assume k is always valid, that is: k ≤ total nodes.

You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example

Example 1:

Input:

{1}

0.000000

1

Output:

[1]

Explanation：

Binary tree {1},  denote the following structure:

1

Example 2:

Input:

{3,1,4,#,2}

0.275000

2

Output:

[1,2]

Explanation：

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

  3

/  \

1    4

\

  2

Challenge

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

思路：

1.用中序遍历一遍二叉树，同时存储下每个节点及其与target的差的绝对值，然后对差进行排序，取前k个，这个时间复杂度大概是O(n + nlogn + k)，效率非常差。

2.依然用中序遍历一遍二叉树，同时找出最接近target的点的坐标，用两根指针从该点坐标往两边走，直到到k为止。这个时间复杂度是O(n + k), 或者中序遍历一遍，再用二分法求最接近target的数，然后用上面方法，时间复杂度时O(n+logn +k)，从量级上来说是一样的。

3.最优算法，时间复杂度 O(k + logn)，空间复杂度 O(logn)

先用两个stack分别走到树的最左端和最右端作为起点，在两个stack中找大于target最小的数和大于target最大的数，找到之后将树看作一个数组，在K的范围内上下移动寻找满足条件的点。

moveUpper(stack) => 根据 stack，挪动到 next node（找该点右子树的最左边的点）

moveLower(stack) => 根据 stack, 挪动到 prev node（找该点左子树的最右边的点）

有了这些函数之后，就可以把整个树当作一个数组一样来处理，只不过每次 i++ 的时候要用 moveUpper，i--的时候要用 moveLower

代码：

思路一：

思路二

思路三：