270. Closest Binary Search Tree Value

tree dfs

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

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, 104].

• 0 <= Node.val <= 109

• -109 <= target <= 109

分析

1. 初始化修正：

   • res 初始化为根节点值，min_diff 初始化为根节点与 target 的差值，避免 inf 导致的逻辑错误。

2. 差值比较逻辑：

   • 直接比较当前节点与 target 的差值，动态更新 res 和 min_diff。

3. 剪枝优化：

   • 根据二叉搜索树（BST）的性质，如果 target < node.val，只需搜索左子树；反之搜索右子树。这可以将时间复杂度从 O(n) 优化到平均 O(log n)。

4. 处理相等差值：

   • 如果多个节点与 target 的差值相同，选择值较小的节点（符合题目要求）。

dfs

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        res = root.val
        diff = abs(root.val - target)

        def dfs(node):
            nonlocal res, diff
            if node is None:
                return
            cur_diff = abs(node.val - target)
            if cur_diff < diff:
                diff = cur_diff
                res = node.val
            elif cur_diff == diff:
                res = min(res, node.val)
            if target < node.val:
                dfs(node.left)
            else:
                dfs(node.right)

        dfs(root)
        return res

iterative

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        res = root.val
        diff = abs(root.val-target)
        while root:
            if abs(root.val - target) < diff:
                res = root.val
                diff = abs(root.val - target)
            elif abs(root.val - target) == diff:
                res = min(res,root.val)
            if root.val > target:
                root = root.left
            else:
                root = root.right
        return res