题目描述
给一棵非空二叉搜索树以及一个target值，找到在BST中最接近给定值的节点值。
给出的目标值为浮点数
可以保证只有唯一一个最接近给定值的节点
测试样例
输入: root = {5,4,9,2,#,8,10} and target = 6.124780
输出: 5
解释：
二叉树 {5,4,9,2,#,8,10}，表示如下的树结构：
5
/ \
4 9
/ / \
2 8 10
输入: root = {3,2,4,1} and target = 4.142857
输出: 4
解释：
二叉树 {3,2,4,1}，表示如下的树结构：
3
/ \
2 4
/
1
解题思路与方法
1、BFS暴力解法
使用BFS将整棵树遍历一遍，在遍历过程中计算每个节点与目标的差值绝对值，并记录下它们的对应关系（可以使用一个dict来记录）。BFS完事后，将记录的最小差值绝对值对应的节点值返回即可。
2、分冶
i). 从根节点开始遍历，每次比较当前节点与目标的大小，若目标值小于当前节点值，则将当前节点当作“上限”，同时将当前节点更新为其左儿子；否则，将当前节点当作“下限”，同时将当前节点更新为其右儿子；
ii). 不断重复i)直至当前节点为空；
iii). 循环结束后，将得到的“上限”与“下限”分别与目标计算差值，若“上限”与目标的差值绝对值较小，则返回这个“上限”对应的值；否则返回“下限”对应的值
代码
1、BFS
from collections import deque
"""
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
@return: the value in the BST that is closest to the target
"""
def closestValue(self, root, target):
if not (root.left and root.right) or target == root:
return root.val
# 记录每个节点元素与target的接近程度，即它们差值的绝对值
delta = {}
q = deque([root])
# BFS
while q:
node = q.popleft()
v = node.val
k = abs(node.val - target)
# key为差值，value为树节点的值
delta[k] = v
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
# 按接近程度排序
sorted_delta = sorted(delta.items(), key=lambda kv: kv[0])
return sorted_delta[0][1]
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
@return: the value in the BST that is closest to the target
"""
def closestValue(self, root, target):
if not (root.left and root.right) or target == root:
return root.val
# 下限
lower = root
# 上限
upper = root
# 当前节点
current = root
while current:
# 目标值小于当前节点
if target < current.val:
# 将当前节点当作上限
upper = current
# 同时将当前节点更新为其左二子
current = current.left
# 目标值大于当前节点
else:
# 将当前节点当作下限
lower = current
# 同时将当前节点更新为其右儿子
current = current.right
lower_win = abs(target - lower.val) < abs(target - upper.val)
return lower.val if lower_win else upper.val
