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.
沿着root向下找即可，每次判段一下是在root左边还是右边。注意没有child的情况。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution(object):
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
#if target == root.val:
# return root.val if target < root.val:
if not root.left:
return root.val
else:
c1 = self.closestValue(root.left, target)
if abs(c1 - target) < abs(root.val - target):
return c1
else:
return root.val
else:
if not root.right:
return root.val
else:
c2 = self.closestValue(root.right, target)
if abs(c2 - target) < abs(root.val - target):
return c2
else:
return root.val