题目描述
给定一棵非空二叉搜索树以及一个target值，找到 BST 中最接近给定值的 k 个数。
给出的target值为浮点数
你可以假设 k 总是合理的，即 k ≤ 总节点数
我们可以保证给出的 BST 中只有唯一一个最接近给定值的 k 个值的集合
假设是一棵平衡二叉搜索树，你可以用时间复杂度低于O(n)的算法解决问题吗( n 为节点个数)？
测试样例
输入:
{1}
0.000000
1
输出:
[1]
解释：
二叉树 {1}，表示如下的树结构：
1
输入:
{3,1,4,#,2}
0.275000
2
输出:
[1,2]
解释：
二叉树 {3,1,4,#,2}，表示如下的树结构：
3
/ \
1 4
\
2
解题思路
1、堆栈
设置两个stack，分别从两个方向寻找与target接近的节点，其中一个存储的值比target大，记为next_stack，另一个则不大于target，记为prev_stack。
先对两个栈进行初始化，当target小于当前节点时，将该节点入栈next_stack，同时将节点置为其左儿子；否则，将该节点入栈prev_stack，并将节点置为其右儿子；重复这个过程直至节点为空。
接下来进入循环，循环k次，代表每轮循环都会找到一个接近target的数。循环一开始先判断两个stack是否都为空，如果是，则跳出循环。
然后，比较两个stack的栈顶与target的接近程度（若其中一个栈为空，则将其余target的差值设置为一个极大值例如sys.maxsize），若prev_stack的栈顶元素与target较接近，则将其加入到结果列表中，同时要在该栈中找到下一个节点；否则，对next_stack进行同样的处理。
最后，待循环结束返回找到的k个数即可。
另外，这里说明下拿出栈顶元素后找到下一个节点的方法，以prev_stack为例：
prev_stack中的值是不大于target的，在初始化的时候。一直是往右子树的方向中找，从而去逼近target。于是，拿出栈顶元素后，就从栈顶的左儿子开始，从这个左儿子往其右子树的方向中去找，每找到一个节点都将其入栈，并将当前节点置为其右儿子，节点为空。
为什么要从栈顶的左儿子开始而不是从其父节点开始呢？因为栈顶是其父节点的右儿子，因此栈顶的左儿子虽比栈顶小但比其父节点还是大的，相比较而言更接近target，因为prev_stack中都是小于target的，所以在prev_stack中，越大就越接近target。
2、先序遍历
从根节点开始往左子树方向遍历，每遇到一个节点就加入栈中，同时将节点更新为左儿子，重复这个过程直至节点为空。
然后，进入循环，直至栈空。每次循环都弹出栈顶，将其加入到结果列表中，使得列表是从小到大排序的。
循环一开始，需要判断下列表中是否已经有超过k个数，如果是并且当前栈顶的这个数与target的接近程度不如列表中的倒数第k个数，那么就可以跳出循环了，因为栈后续的元素都比栈顶大，那么它们与target的接近程度就更加远了。
当栈顶加入到结果列表后，将其更新为右儿子，若右儿子不为空，则入栈，并从这个右儿子的左子树方向一直递归，每到一个节点就将其入栈，直至节点为空。
以上就是每次循环的操作，循环结束后返回结果列表的倒数前k个元素即为所求。
代码
1、堆栈
import sys
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the given BST
@param target: the given target
@param k: the given k
@return: k values in the BST that are closest to the target
"""
def closestKValues(self, root, target, k):
if not root or not k:
return []
closest_ks = []
prev_stack, next_stack = self.bulid_stacks(root, target)
for _ in range(k):
if not (len(prev_stack) or len(next_stack)):
break
delta_prev = abs(prev_stack[-1].val - target) if prev_stack else sys.maxsize
delta_next = abs(next_stack[-1].val - target) if next_stack else sys.maxsize
if delta_prev < delta_next:
closest_ks.append(self.get_prev(prev_stack))
else:
closest_ks.append(self.get_next(next_stack))
return closest_ks
def bulid_stacks(self, node, target):
prev_stack, next_stack = [], []
# 从两个方向逼近target
while node:
# next_stack往值小的方向走，但值比target大
if target < node.val:
next_stack.append(node)
node = node.left
# prev_stack往值大的方向走，但值比target小
else:
prev_stack.append(node)
node = node.right
return prev_stack, next_stack
def get_prev(self, prev_stack):
node = prev_stack.pop()
value = node.val
# prev_stack中，上次已经入栈了所有右子树，
# 因此弹出当前节点后，要继续逼近target，
# 就要从其左儿子的右子树开始
node = node.left
while node:
prev_stack.append(node)
node = node.right
return value
def get_next(self, next_stack):
node = next_stack.pop()
value = node.val
# next_stack中，上次已经入栈了所有左子树
# 因此弹出当前节点后，要继续逼近target，
# 就要从其右儿子的左子树开始
node = node.right
while node:
next_stack.append(node)
node = node.left
return value
2、先序遍历
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the given BST
@param target: the given target
@param k: the given k
@return: k values in the BST that are closest to the target
"""
def closestKValues(self, root, target, k):
ans = []
stack = []
# 先序遍历，从左路一直下去，栈顶获得最小值
while root:
stack.append(root)
root = root.left
while stack:
node = stack.pop()
# ans中的节点是根据值从小到大排序的
# 若当前其中已经超过了k个，并且倒数第k个与target的差
# 已经小于当前栈弹出的节点，那么就已经获得了最接近target的k个数了
# 因为栈之后的节点与target的差都比栈顶的这个节点大
if len(ans) >= k and abs(ans[-k] - target) < abs(node.val - target):
break
ans.append(node.val)
node = node.right
while node:
stack.append(node)
node = node.left
# 最后返回倒数前k嘅数即为所求
return ans[-k:]
