Swift实战：如何优雅地从二叉搜索树中挑出最接近的K个值

摘要

在日常开发中，我们经常会遇到“在一堆数据中找出最接近某个值”的需求。尤其在搜索引擎、推荐系统或者地理坐标匹配中，这种“最近匹配”的问题非常常见。LeetCode 的第 272 题《最接近的二叉搜索树值 II》就是一个很贴近实际的算法题。它要求我们在一个二叉搜索树（BST）里，找出与给定目标值最接近的 K 个数。

这篇文章会带你一步步分析题目，写出 Swift 的题解代码，并配上可运行的 Demo 和测试样例。咱们还会结合实际场景，看看这类问题背后的意义，以及怎么在项目中用起来。

描述

题目要求如下：

给定一个二叉搜索树的根节点 root、一个目标值 target 和一个整数 k，找出 BST 中最接近目标值的 k 个数。

示例：

输入：root = [4,2,5,1,3], target = 3.714286, k = 2
输出：[4,3]

注意：

• 你可以假设 k 总是有效的，1 ≤ k ≤ BST 的总节点数。

• 你可以假设目标值在 BST 中不存在。

• 答案不要求按顺序输出。

题解答案

思路很简单，但实现起来稍有挑战。我们主要有两种策略：

1. 中序遍历 + 排序
   先把所有节点值拿出来，然后根据它们和目标值的差距进行排序，最后返回前 K 个。

2. 使用堆结构进行剪枝优化
   这方法更高效，不需要遍历所有节点，只维护一个大小为 K 的最大堆，保存当前最接近的 K 个值。

考虑到 Swift 标准库里没有原生堆结构，我们这里优先实现第一种“中序遍历 + 排序”的方案，简单直观好调试。

题解代码分析

我们使用中序遍历把 BST 的值按升序放到一个数组里。然后根据每个值与目标值的差异排序，最后取前 K 个。

class TreeNode {var val: Intvar left: TreeNode?var right: TreeNode?init(_ val: Int) {self.val = val}
}class Solution {func closestKValues(_ root: TreeNode?, _ target: Double, _ k: Int) -> [Int] {var nums = [Int]()// 中序遍历func inorder(_ node: TreeNode?) {guard let node = node else { return }inorder(node.left)nums.append(node.val)inorder(node.right)}inorder(root)// 按照和 target 的距离进行排序nums.sort { abs(Double($0) - target) < abs(Double($1) - target) }// 取前 k 个return Array(nums.prefix(k))}
}

示例测试及结果

我们来搭一个简单的树，跑一下这个函数。

// 构建树：[4,2,5,1,3]
let root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left?.left = TreeNode(1)
root.left?.right = TreeNode(3)let sol = Solution()
let result = sol.closestKValues(root, 3.714286, 2)
print(result) // 输出：[4, 3]

运行解释：
中序遍历后我们拿到 [1,2,3,4,5]。对比目标值 3.714286，我们发现 4 和 3 是最接近的两个值，所以返回 [4,3]。

时间复杂度

• 中序遍历：O(n)

• 排序：O(n log n)

• 取前 K 个值：O(k)

总计：O(n log n)，其中 n 是树中节点的数量。

空间复杂度

• 中序遍历需要额外的数组保存所有节点值：O(n)

• 排序过程不需要额外空间（使用原地排序）

总计：O(n)

总结

这道题虽然是一个典型的“树 + 排序”问题，但它的思想可以很好地迁移到很多实际场景里。比如：

• 搜索引擎中找最相关的词条

• 地图里找离当前位置最近的 K 个地标

• 数据监控系统中，找最接近阈值的异常点

我们实现的是中序遍历 + 排序的解法，如果你项目中对性能有要求，可以考虑加上最大堆，剪枝优化进一步降低时间复杂度。

未来展望

如果你希望挑战更复杂的变体，可以试试下面这些：

• 在 BST 中找“最接近目标值的 K 个节点路径”

• 假设树是不断变化的，怎么用优雅的数据结构支持动态查询？

• 加入权重，对“接近”的定义做更多解释（比如偏向大值或小值）