270 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.
The Idea: Perform a regular binary search, except rather than searching for the element explicitly, continually update the closest difference with the target value.
Complexity: O(logN) time and O(|height|) space
class Solution:
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
min_diff = [sys.maxsize]
min_val = [root.val]
def search(root):
if not root:
return
cur_min_diff = abs(root.val - target)
if cur_min_diff < min_diff[0]:
min_diff[0] = cur_min_diff
min_val[0] = root.val
if target < root.val:
return search(root.left)
else:
return search(root.right)
search(root)
return min_val[0]
Python Solution
Same idea, but now iterative.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import sys
class Solution:
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
dist = sys.maxsize
closest_val = sys.maxsize
while root:
cur_dist = abs(root.val - target)
if cur_dist < dist:
closest_val = root.val
dist = cur_dist
if target > root.val:
root = root.right
else:
root = root.left
return closest_val
Last modified 3yr ago