LeetCode 270 最接近的二叉搜索树值（锁题）

朱雀 2022-10-25 14:02 23阅读 0赞

[https://blog.csdn.net/u011646912/article/details/102580812][https_blog.csdn.net_u011646912_article_details_102580812]（转载）

1.题目描述

> 给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。
> 
> 注意：
> 
> 给定的目标值 target 是一个浮点数  
> 题目保证在该二叉搜索树中只会存在一个最接近目标值的数  
> 示例：
> 
> 输入: root = \[4,2,5,1,3\]，目标值 target = 3.714286
> 
> 4  
> / \\  
> 2 5  
> / \\  
> 1 3
> 
> 输出: 4

2.解法

解法一：广度优先搜索
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
     
    class Solution:
        def closestValue(self, root: TreeNode, target: float) -> int:
            if not root:
                return None
            val = root.val
            import sys
            min_ans = sys.maxsize
            while root:
                ans = root.val - target
                if abs(ans) < min_ans:
                    min_ans = abs(ans)
                    val = root.val
                if ans == 0:
                    return root.val
                elif ans > 0:
                    root = root.left
                else:
                    root = root.right
            return val
    解法二：深度优先搜索、递归
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
     
    class Solution:
        def closestValue(self, root: TreeNode, target: float) -> int:
            if not root:
                return None
            a = root.val
            t = root.left if target < a else root.right
            if not t:
                return a
            b = self.closestValue(t, target)
            return a if abs(a-target) < abs(b-target) else b

[https_blog.csdn.net_u011646912_article_details_102580812]: https://blog.csdn.net/u011646912/article/details/102580812