270._Closest_Binary_Search_Tree_Value.md

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