最接近的二叉搜索树值 II

Submission

运行时间: 22 ms

内存: 18.1 MB

# 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 closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
        ans = []
        arr = []
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            arr.append(root.val)
            dfs(root.right)
        dfs(root)
        right = bisect.bisect_left(arr, target)
        left = right - 1

        for i in range(k):
            if left >= 0 and right < len(arr):
                if abs(arr[left]-target) < abs(arr[right]-target):
                    ans.append(arr[left])
                    left -= 1
                else:
                    ans.append(arr[right])
                    right += 1
            elif left >= 0:
                ans.append(arr[left])
                left -= 1
            elif right < len(arr):
                ans.append(arr[right])
                right += 1
        return ans

Explain

这个题解的思路是先通过中序遍历将二叉搜索树转换成一个有序数组，然后利用二分查找找到最接近目标值的位置。接着用双指针从该位置向两边扩展，每次选择与目标值差距更小的那个点加入答案，直至选出 k 个最接近的值。

时间复杂度: O(n + k)

空间复杂度: O(n + k)

# 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 closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
        ans = []
        arr = []
        
        # 中序遍历将二叉搜索树转换成有序数组
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            arr.append(root.val)
            dfs(root.right)
        
        dfs(root)
        
        # 二分查找最接近目标值的位置
        right = bisect.bisect_left(arr, target)
        left = right - 1

        # 双指针扩展并选出 k 个最接近目标值的点
        for i in range(k):
            if left >= 0 and right < len(arr):
                if abs(arr[left]-target) < abs(arr[right]-target):
                    ans.append(arr[left])
                    left -= 1
                else:
                    ans.append(arr[right])
                    right += 1
            elif left >= 0:
                ans.append(arr[left])
                left -= 1
            elif right < len(arr):
                ans.append(arr[right])
                right += 1
        
        return ans

Explore

在二叉搜索树（BST）中，中序遍历的过程会按照从小到大的顺序访问所有节点，这是因为对于任何一个节点，中序遍历先访问其左子树，然后是节点本身，最后是右子树。这样的访问顺序恰好符合二叉搜索树的有序性质。相比之下，前序和后序遍历则无法保证输出一个有序数组，因为它们访问节点的顺序与节点的大小顺序不一致。例如，前序遍历首先访问根节点，然后是左子树和右子树，这不会直接产生有序数组。因此，中序遍历是转换BST为有序数组的最自然和直接的方法。

`bisect_left`函数在数组中找到第一个不小于目标值的元素的位置，而`bisect_right`则找到第一个大于目标值的元素的位置。使用`bisect_left`意味着如果目标值正好等于数组中的某个元素，那么返回的位置将是这些相等元素的最左侧位置。这种选择有助于在后续双指针过程中更平均地考虑目标值两侧的元素，避免偏向任一侧。如果使用`bisect_right`，则在相等元素较多的情况下可能跳过最接近的一侧，从而可能影响结果的最优性。

在双指针过程中，如果一个指针（`left`或`right`）越界，程序会继续移动另一个仍在数组范围内的指针，直到收集到足够的k个元素。例如，如果`left`指针越界（小于0），则只增加`right`指针，反之亦然。由于数组已经包含了所有树节点的值，这种方法保证了即使一个方向的指针越界，仍然可以从另一方向获取足够的元素来满足k的需求。

是的，二分查找和双指针策略仍然有效。二分查找通过`bisect_left`找到最接近目标值的起始位置，即便这个位置的元素值不完全等于目标值。之后，双指针策略从这个位置开始向两边扩展，比较左右元素与目标值的差距，逐步选择最接近的元素。这种方法确保了即使目标值不等于任何节点值，也能找到最接近的k个值。