摘要

在日常開發中，我們經常會遇到“在一堆數據中找出最接近某個值”的需求。尤其在搜索引擎、推薦系統或者地理坐標匹配中，這種“最近匹配”的問題非常常見。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 個節點路徑”

• 假設樹是不斷變化的，怎么用優雅的數據結構支持動態查詢？

• 加入權重，對“接近”的定義做更多解釋（比如偏向大值或小值）