lintcode900

Description

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

Example

Given root = {1}, target = 4.428571, return 1.

Idea

思路很简单，就是找到通过检索BST找到upper bound和lower bound，最后在比较谁是离得最近的。upper bound的意思是在整棵树里面，比target小却最大的数，lower bound的意思是在整棵树里面比target大的最小的数。这个大小关系是，进一步递归检索的关键。

Code

"""
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):
        # write your code here
        if root is None:
            return
        
        lower_node = self.lower_bound(root, target)
        upper_node = self.upper_bound(root, target)
        
        if lower_node is None:
            return upper_node.val

        if upper_node is None:
            return lower_node.val    
    
        if lower_node and upper_node:
            if target - lower_node.val > upper_node.val - target:
                return upper_node.val
            else:
                return lower_node.val
            
        return None
        
    
    # find the node with the largest value that smaller than target
    def lower_bound(self, root, target):
        if root is None:
            return None
        
        # the expect val should be smaller than or equal to target
        if root.val > target:
            return self.lower_bound(root.left, target)
        
        # the largest val
        lower_node = self.lower_bound(root.right, target)
        if lower_node:
            return lower_node
        
        # if lower_node is None, the there's no node larger than root, so return root
        return root
    
    
    # find the node with the smallest value that larger than or equal to target
    def upper_bound(self, root, target):
        if root is None:
            return None
        
        # the expect val should be larger than or equal to target
        if root.val < target:
            return self.upper_bound(root.right, target)
        
        # the smallest val
        upper_node = self.upper_bound(root.left, target)
        if upper_node:
            return upper_node
            
        return root