# 270. Closest Binary Search Tree Value

## 刷题内容

• https://leetcode.com/problems/closest-binary-search-tree-value

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

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

4
/ \
2   5
/ \
1   3

Output: 4


## 解题方案

class Solution(object):
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
res, diff = [], []
self.inorder(root, res)

for i in res:
diff.append(abs(i-target))
return res[diff.index(min(diff))]

def inorder(self, root, res):
if not root:
return
self.inorder(root.left, res)
res.append(root.val)
self.inorder(root.right, res)


class Solution(object):
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
lst = []

def inorder(root):
if root:
inorder(root.left)
lst.append(root.val)
inorder(root.right)

inorder(root)

close = lst[0]
diff = abs(target - lst[0])

for i in lst:
if abs(target - i) < diff:
close = i
diff = abs(target - i )

return close


AC代码，跟binary search tree 寻值一样, loop 一遍树来寻找

class Solution(object):
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
close = root.val

while root:
close = root.val if abs(target - root.val) < abs(target - close) else close
root = root.right if root.val < target else root.left
return close