E-NR270. Closest Binary Search Tree Value

https://leetcode.com/problems/closest-binary-search-tree-value/leetcode.com

float('inf')

float('inf')=float('+inf')正无穷

float('-inf')负无穷

思考:写到这里, 发现每个树的递归都能至少用四种方法写(分别是回囘囬廻):

即用

• 带helper与否

• if root 输出或者 if not root输出.

# 1 不要helper, 直接拿全局变量操作
class Solution:
    def __init__(self):
        self.diff = float('inf')
        self.node = None
        
    def closestValue(self, root: TreeNode, target: float) -> int:
        if not root:
            return None
        
        self.closestValue(root.left, target)
        
        cur_diff = self.diff
        self.diff = min(self.diff, abs(target-root.val))
        if cur_diff == self.diff:
            return self.node.val
        else:
            self.node = root
            
        self.closestValue(root.right, target)
        return self.node.val

# or 1(if root版本):
class Solution:
    def __init__(self):
        self.diff = float('inf')
        self.node = None
        
    def closestValue(self, root: TreeNode, target: float) -> int:
        if root:
            self.closestValue(root.left, target)
            
            cur_diff = self.diff
            self.diff = min(self.diff, abs(target-root.val))
            if cur_diff == self.diff:
                return self.node.val
            else:
                self.node = root
                
            self.closestValue(root.right, target)
            return self.node.val
        else:
            return None
            
# 2 带helper的:
class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        def find_closest(root, closest_node, min_diff):
            if not root:
                return closest_node, min_diff 
            
            closest_node, min_diff = find_closest(root.left, closest_node, min_diff)
            
            cur_diff = min_diff
            min_diff = min(abs(target-root.val), cur_diff)
            if min_diff == cur_diff:
                return closest_node, min_diff
            else:
                closest_node = root
            
            closest_node, min_diff = find_closest(root.right, closest_node, min_diff)
            return closest_node, min_diff
        
        a, b = find_closest(root, None, float('inf'))
        
        return a.val

# 2 同理有个if root版本, 不赘述了

# 别人的一些答案, 学习一下:
class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        cur = float('-inf')
        return self.inorder(root, target, cur)
    def inorder(self, root, target, cur):
        if root is None: 
            return cur
        cur = self.inorder(root.left, target, cur)
        if abs(cur-target) > abs(root.val - target):
            cur = root.val
        else:
            return cur
        return self.inorder(root.right, target, cur)
            
class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = None
        minVal = float('inf')
        while root:
            if minVal > abs(root.val - target):
                minVal = abs(root.val - target)
                closest = root.val
            if root.val >= target:
                root = root.left
            elif root.val < target:
                root = root.right
        return closest
        
class Solution:
    def closestValue(self, root, target):
        self.closest = float('inf')
        
        def helper(root, value):
            if not root:
                return
            if abs(root.val - target) < abs(self.closest - target):
                self.closest = root.val
                
            # Target should be located on left subtree
            if target < root.val:
                helper(root.left, target)
                
            # target should be located on right subtree
            if target > root.val:
                helper(root.right, target)
        
        helper(root, target)
        return self.closest