给定一棵非空二叉搜索树以及一个target值，找到 BST 中最接近给定值的 k 个数。
样例 1:
输入:
{1}
0.000000
1
输出:
[1]
解释：
二叉树 {1}，表示如下的树结构：
1
样例 2:
输入:
{3,1,4,#,2}
0.275000
2
输出:
[1,2]
解释：
二叉树 {3,1,4,#,2}，表示如下的树结构：
3
/ 1 4
2
假设是一棵平衡二叉搜索树，你可以用时间复杂度低于O(n)的算法解决问题吗( n 为节点个数)？
k 总是合理的，即 k ≤ 总节点数唯一一个最接近给定值的 k 个值的集合"""
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 root is None or k == 0:
return []
nums = self.get_inorder(root)
left = self.find_lower_index(nums, target)
right = left + 1
results = []
for _ in range(k):
if (right >= len(nums)) or (left >=0 and target - nums[left] < nums[right] - target):
results.append(nums[left])
left -= 1
else:
results.append(nums[right])
right += 1
return results
def get_inorder(self, root):
result = []
stack = []
node = root
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
result.append(node.val)
node = node.right
return result
def find_lower_index(self, nums, target):
"""
find the largest number < target, return the index
"""
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] < target:
start = mid
else:
end = mid
if nums[end] < target:
return end
if nums[start] < target:
return start
return -1
更优的解法，todo
相关的题目：
给定一个二叉查找树和范围[k1, k2]。按照升序返回给定范围内的节点值。
样例 1:
输入：{5},6,10
输出：[]
5
它将被序列化为 {5}
没有数字介于6和10之间
样例 2:
输入：{20,8,22,4,12},10,22 输出：[12,20,22] 解释： 20 / 8 22 / 4 12 它将被序列化为 {20,8,22,4,12} [12,20,22]介于10和22之间
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: param root: The root of the binary search tree
@param k1: An integer
@param k2: An integer
@return: return: Return all keys that k1<=key<=k2 in ascending order
"""
def searchRange(self, root, k1, k2):
# write your code here
"""
# recursive solution
if not root:
return []
if root.val < k1:
return self.searchRange(root.right, k1, k2)
elif root.val > k2:
return self.searchRange(root.left, k1, k2)
else:
return self.searchRange(root.left, k1, k2) + [root.val] + self.searchRange(root.right, k1, k2)
"""
result = []
q = [root]
while q:
node = q.pop()
if not node:
continue
if k1 <= node.val <= k2:
result.append(node.val)
q.append(node.left)
q.append(node.right)
elif node.val < k1:
q.append(node.right)
else:
q.append(node.left)
result.sort()
return result
原文：https://www.cnblogs.com/bonelee/p/11632584.html