Closest Binary Search Tree Value

二分搜索找那个差距最小的值就行了

class Solution(object):
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        distance = sys.maxint
        result = root.val
        while root:
            if abs(target - root.val) < distance:
                distance = abs(target - root.val)
                result = root.val
            if target > root.val:
                root = root.right
            else:
                root = root.left

        return result

Closest Binary Search Tree Value II

这题的解法太多了，首先可以明确一个思路，这个target值有可能存在三种情况，第一种落在BST的最小值左侧，第二种落在最大值右侧，第三种落在范围之间，但无论何种情况，我们要的都是最接近这个值的k个数，既然如此，我们可以利用一个双端队列或者长度为k的定长list来维护当前最接近的k个数，这里又有一个规律，即如果当前元素与目标值的距离的绝对值既大于list的头元素也大于尾元素和目标的距离绝对值，则我们可以直接返回了，因为按照BST的顺序定义，后面的值差距只会越来越大，所以这里其实就衍生了很多种做法，首先可以把BST中序遍历一遍记录下来所有值，再通过数组来维护k个结果，也可以一遍遍历一边维护，同时我们还可以根据差距值建一个最小堆来逐个吐出结果，最后我们还可以模仿sliding window median那样用一个栈储存所有小于目标值的元素，再用一个栈储存所有大于目标值的元素，每次对比之后吐出需要结果，这里现在只做了第一种最朴素的方法

class Solution(object):
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        tmp = []
        original = []
        stack = []
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                print root.val
                tmp.append(root.val - target)
                original.append(root.val)
                root = root.right

        stack = collections.deque([])
        count = 0
        for index, num in enumerate(tmp):
            if count < k:
                stack.append(index)
                count += 1
            elif abs(tmp[stack[0]]) > abs(num) or abs(tmp[stack[-1]]) > abs(num):
                stack.popleft()
                stack.append(index)
            else:
                break

        return [original[x] for x in stack]