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
解题方案
思路 1
来个中序遍历，再判断哪个最close
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)
思路 2
或者可以用更节省空间的方式，只保留一个closet，不断比较
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
思路 3
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
