LeetCode 270 Closest Binary Search Tree Value

LeetCode

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

Constraints: The number of nodes in the tree is in the range [1, 10<sup>4</sup>]. 0 <= Node.val <= 10<sup>9</sup> * -10<sup>9</sup> <= target <= 10<sup>9</sup>

题目大意：

求BST中最接近target的值

解题思路：

接近target的值在BST搜索路径上，越后搜索到的(越后入栈的)越接近，但最接近的可能大于或小于target(predecessors or successors)，只能逐一比较.
类似于LeetCode 272 Closest Binary Search Tree Value II

解题步骤：

N/A

注意事项：

1. 循环中用it，不能用root，注意检查
2. 接近target的值在BST搜索路径上，逐一比较

Python代码：

def closestValue(self, root: TreeNode, target: float) -> int:
	closest_vals = []
	it = root
	while it:
		closest_vals.append(it.val)
		if target < it.val:
			it = it.left
		else:
			it = it.right
	min_val, res = float('inf'), 0
	for n in closest_vals:
		if abs(target - n) < min_val:
			min_val = abs(target - n)
			res = n
	return res

算法分析：

时间复杂度为O(h)，空间复杂度O(h)