*270 Closest Binary Search Tree Value
https://leetcode.com/problems/closest-binary-search-tree-value/
solution
class Solution:
def closestValue(self, root, target):
upper = root
lower = root
while root:
if root.val > target:
upper = root # 先记录再往后迭代
root = root.left
elif root.val < target:
lower = root
root = root.right
else:
return root.val
if abs(upper.val - target) > abs(lower.val - target):
return lower.val
return upper.val
# 一些BST题目甚至可以先中序存为list, 再从list中找到最近的
class Solution(object):
def closestValue(self, root, target):
res = None
cur = root
while cur:
# 更直接的思路: 记录遍历过程中距离, 并记录更新距离最小的dian
if res is None or abs(res - target) > abs(cur.val - target):
res = cur.val
if cur.val > target:
cur = cur.left
else:
cur = cur.right
return res
时间复杂度:O(h) 空间复杂度:O(h)
dfs
class Solution:
def __init__(self):
self.low = -float('inf')
self.high = float('inf')
def closest_value(self, root: TreeNode, target: float) -> int:
if not root:
return
if root.val <= target:
self.low = max(self.low, root.val)
self.closest_value(root.right, target)
else:
self.high = min(self.high, root.val)
self.closest_value(root.left, target)
if target - self.low > self.high -target:
return self.high
else:
return self.low
follow up
272. Closest Binary Search Tree Value II
Last updated