首页 > 代码库 > Leetcode 270. Closest Binary Search Tree Value
Leetcode 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.
沿着root向下找即可,每次判段一下是在root左边还是右边。注意没有child的情况。
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 8 class Solution(object): 9 def closestValue(self, root, target): 10 """ 11 :type root: TreeNode 12 :type target: float 13 :rtype: int 14 """ 15 #if target == root.val: 16 # return root.val 17 18 if target < root.val: 19 if not root.left: 20 return root.val 21 else: 22 c1 = self.closestValue(root.left, target) 23 if abs(c1 - target) < abs(root.val - target): 24 return c1 25 else: 26 return root.val 27 else: 28 if not root.right: 29 return root.val 30 else: 31 c2 = self.closestValue(root.right, target) 32 if abs(c2 - target) < abs(root.val - target): 33 return c2 34 else: 35 return root.val
Leetcode 270. Closest Binary Search Tree Value
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。