LeetCode 272 详解二叉搜索树中距离 target 最近的 k 个值Closest Binary Search Tree Value II五种解法全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以仓库中 closest-binary-search-tree-value-ii.md 为主体系统讲解 LeetCode 272「二叉搜索树中最接近目标值的 k 个数」的五种经典解法。通过完整阅读本文你将掌握如何利用 BST 的中序遍历有序性、堆的 Top-K 维护、双指针滑动窗口与二分查找等技巧把朴素的全量排序方案逐步优化到 O(n) 时间并规避离一错误、堆类型选错等高频陷阱。问题与前置知识题目核心给定一棵二叉搜索树的根节点root、一个浮点型目标值target和整数k返回树中与target距离绝对值差最近的k个节点值。与只找一个最接近值的 closest-binary-search-tree-value.mdClosest BST Value I不同本题需要返回一个长度为k的集合。在动手写代码前需要熟悉以下基础二叉搜索树性质任意节点的左子树值均小于该节点、右子树值均大于该节点因此中序遍历得到的是升序序列——这是后续所有高效解法的根基中序遍历按左子树 → 当前节点 → 右子树的顺序处理节点可在 O(n) 时间内产出有序数组二分查找在有序数组中定位target的插入点从而确定最接近元素的位置堆 / 优先队列用大小为 k 的最大堆维护当前最接近的 k 个值堆顶即距离最远的元素便于淘汰双指针 / 滑动窗口从插入点向两侧扩张逐个收集距离更近的值。仓库 README.md 将该仓库定位为 NeetCode 的 LeetCode 多语言题解集合下文每种解法均按直觉 → 算法步骤 → 代码 → 复杂度的结构展开代码以 Python 为主同时说明各语言实现中的关键差异。解法一收集全量节点 自定义比较器排序O(n log n)直觉最直观的思路是先把树里所有节点值收集起来再按照与 target 的绝对距离排序排在最前面的 k 个即为答案。这种做法完全不依赖树的形状因为题目只关心值离 target 近不近不关心节点在树中的位置。算法步骤DFS 遍历整棵树把所有节点值收集进数组用自定义比较器按abs(值 - target)升序排序距离相同时取更小值返回排序后数组的前 k 个元素。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, arr): if not node: return arr.append(node.val) dfs(node.left, arr) dfs(node.right, arr) arr [] dfs(root, arr) arr.sort(key lambda x: (abs(x - target), x)) return arr[:k]语言实现要点Java 使用Collections.sort(arr, (o1, o2) - Math.abs(o1 - target) Math.abs(o2 - target) ? -1 : 1)注意比较器需保证传递性C 用sort(arr.begin(), arr.end(), { return abs(a - target) abs(b - target); })随后vectorint(arr.begin(), arr.begin() k)截取前 k 个Go 用sort.Slice(arr, func(i, j int) bool { return math.Abs(float64(arr[i])-target) math.Abs(float64(arr[j])-target) })Rust 的排序键需要把f64距离通过partial_cmp比较并用.then(a.cmp(b))处理距离相同时的字典序见原文档对应实现。复杂度分析时间复杂度O(n log n)瓶颈在排序收集本身只需 O(n)空间复杂度O(n)需要存储全部 n 个节点值。其中 n 为树中节点总数。解法二DFS 遍历 大小为 k 的最大堆O(n log k)直觉排序整个数组是杀鸡用牛刀——我们只需要 k 个最接近的值没必要对所有 n 个值排序。改用容量为 k 的最大堆堆按与 target 的距离排序堆顶永远是当前窗口中距离最远的元素。遍历过程中一旦发现更近的新节点就淘汰堆顶始终保持堆内恰好是已见过的、最接近 target 的 k 个值。算法步骤创建按距离降序排列距离最远在堆顶的最大堆DFS 遍历所有节点每个节点值入堆若堆大小超过k弹出距离最远的堆顶元素遍历结束后堆中剩余元素即为答案。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, heap): if not node: return if len(heap) k: heappush(heap, (-abs(node.val - target), node.val)) else: if abs(node.val - target) abs(heap[0][0]): heappop(heap) heappush(heap, (-abs(node.val - target), node.val)) dfs(node.left, heap) dfs(node.right, heap) heap [] dfs(root, heap) return [x[1] for x in heap]Python 的heapq只提供最小堆因此用取负距离-abs(node.val - target)实现最大堆语义堆顶元组的距离绝对值最小即原距离最大正是要淘汰的最远者。语言实现要点C 使用priority_queueint, vectorint, decltype(cmp) heap(cmp)cmp定义abs(a - target) abs(b - target)使距离最小者沉底、距离最大者在堆顶heap.pop()弹出最远元素Java 用PriorityQueue((a, b) - Math.abs(a - target) Math.abs(b - target) ? -1 : 1)构造最大堆heap.remove()弹出堆顶Go 需要手写实现heap.Interface的maxHeap类型Less中返回距离更大者优先完整代码见原文档Rust 中因f64不实现Ord采用((val - target).abs() * 1_000_000.0) as i64把距离缩放为整数后放入BinaryHeap(i64, i32)这是一个值得借鉴的浮点排序工程技巧。复杂度分析时间复杂度O(n log k)每个节点至多触发一次堆调整log k空间复杂度O(n k)堆本身占用 k递归调用栈最坏 O(n)。其中 n 为节点数k 为堆的容量。解法三中序遍历 二分定位 双指针滑动窗口O(n k)直觉既然中序遍历天然给出有序数组那么k 个最接近 target 的值在有序数组中必然是连续的一段子数组这是单调性的直接推论。于是问题转化为先定位 target 的插入点再以该位置为中心用两个指针向左右两侧贪心扩张每次取距离更近的一侧直到集满 k 个。算法步骤中序遍历得到升序数组arr二分查找target的插入位置初始化left指向插入点前一个元素、right指向插入点比较arr[left]与arr[right]谁离 target 更近取近者并让对应指针向外移动重复直到收集满 k 个。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, arr): if not node: return dfs(node.left, arr) arr.append(node.val) dfs(node.right, arr) arr [] dfs(root, arr) left bisect_left(arr, target) - 1 right left 1 ans [] while len(ans) k: if right len(arr) or abs(arr[left] - target) abs(arr[right] - target): ans.append(arr[left]) left - 1 else: ans.append(arr[right]) right 1 return ans语言实现要点该解法对越界处理要求严格C 版在每次比较前先判断left 0与right arr.size()两个边界分别退化为只取右侧或只取左侧Java 版先线性扫描找到距离最小值的索引start作为窗口中心再向两侧扩张二分定位在 JavaScript 中以手写的bisectLeft实现lo/hi双端逼近Go 用sort.Search(len(arr), func(i int) bool { return float64(arr[i]) target }) - 1Kotlin 用arr.binarySearch(target.toInt())的返回值换算插入点。复杂度分析时间复杂度O(n k)中序遍历 O(n)双指针扩张至多 O(k) 次空间复杂度O(n)。其中 n 为节点数k 为滑窗大小。解法四二分搜索窗口左边界O(n) / O(n k)直觉解法三需要先定位插入点再向两侧扩张而解法四更进一步直接二分搜索长度为 k 的连续窗口的最优左边界。因为答案是一个连续子数组只需确定它的起点left。判断标准是对任意候选起点mid比较窗口左端arr[mid]与若窗口右移一位会新增的arr[mid k]——若后者离 target 更近说明窗口整体右移更优否则保持左移。算法步骤中序遍历得到升序数组arr二分搜索窗口左边界搜索范围是索引0到n - k对每个中点mid比较arr[mid k]与arr[mid]的距离若mid k处更近则窗口向右收缩left mid 1否则向左收缩right mid返回从最终左边界开始、长度为 k 的子数组。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, arr): if not node: return dfs(node.left, arr) arr.append(node.val) dfs(node.right, arr) arr [] dfs(root, arr) left 0 right len(arr) - k while left right: mid (left right) // 2 if abs(target - arr[mid k]) abs(target - arr[mid]): left mid 1 else: right mid return arr[left:left k]正确性直觉在单调递增的arr上abs(target - arr[i])关于i先递减后递增V 形。若arr[mid k]比arr[mid]更近说明 V 形谷底在mid右侧最优窗口左边界必大于mid反之谷底在mid处或左侧收缩右边界。这与经典寻找山谷二分完全同构。语言实现要点C 使用lower_bound(arr.begin(), arr.end(), target)定位插入点后再进入窗口二分Java 直接以0与arr.size() - k为搜索区间Rust 使用arr.partition_point(|x| (x as f64) target)求出插入位置再执行同样的窗口二分原文档标注该解法在 Java 中时间复杂度为O(n)中序遍历为主二分仅 log n 次比较在 Python 中切片arr[left:left k]额外复制 k 个元素因此记作O(n k)。复杂度分析时间复杂度O(n)Java/ O(n k)Python其中 n 为节点数、k 为返回元素个数空间复杂度O(n)存放有序数组。解法五中序遍历 双端队列Deque构建窗口O(n)直觉解法三、四都依赖先完整中序收集再处理解法五把两者合二为一在遍历的同时维护一个容量为 k 的双端队列。由于中序访问顺序就是升序队列前端始终是当前窗口的最小值最早加入、后端是最大值最新加入。当队列超过 k 个元素时比较首尾元素的距离淘汰距离更远的那一端。更关键的是一旦发现队首元素离 target 更近或相等由于后续访问的值只会更大、离 target 更远可以提前终止右子树遍历避免无谓的访问。算法步骤中序遍历整棵树用双端队列维护当前候选窗口每访问一个节点将其值从队尾入队若队列大小超过 k比较队首与队尾到 target 的距离——若队首更近或相等移除队尾并停止遍历右子树否则移除队首并继续遍历结束队列中即为答案。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, queue): if not node: return dfs(node.left, queue) queue.append(node.val) if len(queue) k: if (abs(target - queue[0]) abs(target - queue[-1])): queue.pop() return else: queue.popleft() dfs(node.right, queue) queue deque() dfs(root, queue) return list(queue)语言实现要点Java 使用DequeInteger queue new LinkedList()通过peekFirst()/peekLast()读端、removeFirst()/removeLast()淘汰C 用dequeintfront()/back()读取、pop_front()/pop_back()淘汰注意这里的return是函数级返回用于剪掉整棵右子树Go 用切片模拟双端队列queue queue[1:]弹出队首、queue queue[:len(queue)-1]弹出队尾Rust 使用VecDequei32与pop_front()/pop_back()语义与 Python 完全一致。复杂度分析时间复杂度O(n)每个节点至多入队一次且多数情况下能提前剪枝空间复杂度O(n k)队列容量 k递归栈最坏 O(n)。其中 n 为节点数k 为返回元素个数。五种解法复杂度对比解法核心思路时间复杂度空间复杂度适用场景1. 自定义比较器排序DFS 收集 全量排序O(n log n)O(n)代码最简适合小规模数据与面试热身2. 大小为 k 的最大堆遍历中维护 Top-KO(n log k)O(n k)不想依赖中序有序性时的通用方案3. 中序遍历 双指针二分定位 两侧扩张O(n k)O(n)充分利用 BST 有序性思路直观4. 二分搜索左边界直接二分窗口起点O(n) / O(n k)O(n)在有序数组上把问题收敛为一次二分5. 中序遍历 Deque遍历中动态维护窗口O(n)O(n k)兼顾时间最优与提前剪枝工程上最优雅n 为树中节点数k 为需要返回的最接近值个数。当树高度不平衡时解法二、五的递归栈深度会退化到 O(n)。常见陷阱Common Pitfalls1. 未利用 BST 性质用通用遍历 全量排序虽然正确却丢失了 BST 特有的 O(n k) 优化空间。中序遍历得到有序数组是本题由 O(n log n) 跃升到 O(n) 的关键任何不使用该性质的方案都值得重新审视。2. 二分搜索中的离一错误Off-by-One用二分定位插入点时插入点可能落在索引 0 或 n 处导致左指针初始化为 -1 或右指针越界# 错误可能产生索引 -1 访问 left bisect_left(arr, target) - 1 # 若 target 小于所有元素left -1 # 必须先判断left 0 时直接访问 arr[left] 会越界解法三的 C/JavaScript/Go 实现均对此做了显式分支处理left 0时只取右侧、right arr.size()时只取左侧。3. 堆类型选错用成最小堆用堆维护 k 个最近值时必须用最大堆来淘汰距离最远的元素。若误用最小堆弹出的反而是距离最近的元素结果完全错误# 错误最小堆会淘汰最近的值 heappush(heap, (abs(node.val - target), node.val)) # 正确最大堆距离取负淘汰最远的值 heappush(heap, (-abs(node.val - target), node.val))4. 相等距离的决胜处理不正确当两个值与 target 距离相等时按题目要求应返回较小值。Python 解法一通过key lambda x: (abs(x - target), x)的元组排序天然处理了决胜其余解法在与的边界语义上需要仔细核对否则在对称输入如 target 恰为两数中点时可能返回错误集合。5. 双指针提前停止、漏掉另一侧在滑动窗口解法中若某一侧指针先越界就立刻停止收集会漏掉另一侧本应入选的元素。正确做法是一侧越界后继续从另一侧单调取数直到集满 k 个解法三各语言实现中均有体现。延伸阅读本题的单值版本返回 1 个最接近值详见 closest-binary-search-tree-value.md其中包含递归中序 线性扫描、迭代中序提前终止O(k)、以及沿单条路径二分O(H)三种递进思路是理解本题由找 1 个推广到找 k 个的最佳铺垫本文完整的多语言实现Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust均收录于 closest-binary-search-tree-value-ii.md仓库根目录 README.md 维护了全部题目的多语言覆盖率总表可按语言目录如python/、cpp/、go/、rust/继续检索相邻的 BST 题目源码。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 272 详解：二叉搜索树中距离 target 最近的 k 个值（Closest Binary Search Tree Value II）五种解法全解析
LeetCode 272 详解二叉搜索树中距离 target 最近的 k 个值Closest Binary Search Tree Value II五种解法全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以仓库中 closest-binary-search-tree-value-ii.md 为主体系统讲解 LeetCode 272「二叉搜索树中最接近目标值的 k 个数」的五种经典解法。通过完整阅读本文你将掌握如何利用 BST 的中序遍历有序性、堆的 Top-K 维护、双指针滑动窗口与二分查找等技巧把朴素的全量排序方案逐步优化到 O(n) 时间并规避离一错误、堆类型选错等高频陷阱。问题与前置知识题目核心给定一棵二叉搜索树的根节点root、一个浮点型目标值target和整数k返回树中与target距离绝对值差最近的k个节点值。与只找一个最接近值的 closest-binary-search-tree-value.mdClosest BST Value I不同本题需要返回一个长度为k的集合。在动手写代码前需要熟悉以下基础二叉搜索树性质任意节点的左子树值均小于该节点、右子树值均大于该节点因此中序遍历得到的是升序序列——这是后续所有高效解法的根基中序遍历按左子树 → 当前节点 → 右子树的顺序处理节点可在 O(n) 时间内产出有序数组二分查找在有序数组中定位target的插入点从而确定最接近元素的位置堆 / 优先队列用大小为 k 的最大堆维护当前最接近的 k 个值堆顶即距离最远的元素便于淘汰双指针 / 滑动窗口从插入点向两侧扩张逐个收集距离更近的值。仓库 README.md 将该仓库定位为 NeetCode 的 LeetCode 多语言题解集合下文每种解法均按直觉 → 算法步骤 → 代码 → 复杂度的结构展开代码以 Python 为主同时说明各语言实现中的关键差异。解法一收集全量节点 自定义比较器排序O(n log n)直觉最直观的思路是先把树里所有节点值收集起来再按照与 target 的绝对距离排序排在最前面的 k 个即为答案。这种做法完全不依赖树的形状因为题目只关心值离 target 近不近不关心节点在树中的位置。算法步骤DFS 遍历整棵树把所有节点值收集进数组用自定义比较器按abs(值 - target)升序排序距离相同时取更小值返回排序后数组的前 k 个元素。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, arr): if not node: return arr.append(node.val) dfs(node.left, arr) dfs(node.right, arr) arr [] dfs(root, arr) arr.sort(key lambda x: (abs(x - target), x)) return arr[:k]语言实现要点Java 使用Collections.sort(arr, (o1, o2) - Math.abs(o1 - target) Math.abs(o2 - target) ? -1 : 1)注意比较器需保证传递性C 用sort(arr.begin(), arr.end(), { return abs(a - target) abs(b - target); })随后vectorint(arr.begin(), arr.begin() k)截取前 k 个Go 用sort.Slice(arr, func(i, j int) bool { return math.Abs(float64(arr[i])-target) math.Abs(float64(arr[j])-target) })Rust 的排序键需要把f64距离通过partial_cmp比较并用.then(a.cmp(b))处理距离相同时的字典序见原文档对应实现。复杂度分析时间复杂度O(n log n)瓶颈在排序收集本身只需 O(n)空间复杂度O(n)需要存储全部 n 个节点值。其中 n 为树中节点总数。解法二DFS 遍历 大小为 k 的最大堆O(n log k)直觉排序整个数组是杀鸡用牛刀——我们只需要 k 个最接近的值没必要对所有 n 个值排序。改用容量为 k 的最大堆堆按与 target 的距离排序堆顶永远是当前窗口中距离最远的元素。遍历过程中一旦发现更近的新节点就淘汰堆顶始终保持堆内恰好是已见过的、最接近 target 的 k 个值。算法步骤创建按距离降序排列距离最远在堆顶的最大堆DFS 遍历所有节点每个节点值入堆若堆大小超过k弹出距离最远的堆顶元素遍历结束后堆中剩余元素即为答案。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, heap): if not node: return if len(heap) k: heappush(heap, (-abs(node.val - target), node.val)) else: if abs(node.val - target) abs(heap[0][0]): heappop(heap) heappush(heap, (-abs(node.val - target), node.val)) dfs(node.left, heap) dfs(node.right, heap) heap [] dfs(root, heap) return [x[1] for x in heap]Python 的heapq只提供最小堆因此用取负距离-abs(node.val - target)实现最大堆语义堆顶元组的距离绝对值最小即原距离最大正是要淘汰的最远者。语言实现要点C 使用priority_queueint, vectorint, decltype(cmp) heap(cmp)cmp定义abs(a - target) abs(b - target)使距离最小者沉底、距离最大者在堆顶heap.pop()弹出最远元素Java 用PriorityQueue((a, b) - Math.abs(a - target) Math.abs(b - target) ? -1 : 1)构造最大堆heap.remove()弹出堆顶Go 需要手写实现heap.Interface的maxHeap类型Less中返回距离更大者优先完整代码见原文档Rust 中因f64不实现Ord采用((val - target).abs() * 1_000_000.0) as i64把距离缩放为整数后放入BinaryHeap(i64, i32)这是一个值得借鉴的浮点排序工程技巧。复杂度分析时间复杂度O(n log k)每个节点至多触发一次堆调整log k空间复杂度O(n k)堆本身占用 k递归调用栈最坏 O(n)。其中 n 为节点数k 为堆的容量。解法三中序遍历 二分定位 双指针滑动窗口O(n k)直觉既然中序遍历天然给出有序数组那么k 个最接近 target 的值在有序数组中必然是连续的一段子数组这是单调性的直接推论。于是问题转化为先定位 target 的插入点再以该位置为中心用两个指针向左右两侧贪心扩张每次取距离更近的一侧直到集满 k 个。算法步骤中序遍历得到升序数组arr二分查找target的插入位置初始化left指向插入点前一个元素、right指向插入点比较arr[left]与arr[right]谁离 target 更近取近者并让对应指针向外移动重复直到收集满 k 个。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, arr): if not node: return dfs(node.left, arr) arr.append(node.val) dfs(node.right, arr) arr [] dfs(root, arr) left bisect_left(arr, target) - 1 right left 1 ans [] while len(ans) k: if right len(arr) or abs(arr[left] - target) abs(arr[right] - target): ans.append(arr[left]) left - 1 else: ans.append(arr[right]) right 1 return ans语言实现要点该解法对越界处理要求严格C 版在每次比较前先判断left 0与right arr.size()两个边界分别退化为只取右侧或只取左侧Java 版先线性扫描找到距离最小值的索引start作为窗口中心再向两侧扩张二分定位在 JavaScript 中以手写的bisectLeft实现lo/hi双端逼近Go 用sort.Search(len(arr), func(i int) bool { return float64(arr[i]) target }) - 1Kotlin 用arr.binarySearch(target.toInt())的返回值换算插入点。复杂度分析时间复杂度O(n k)中序遍历 O(n)双指针扩张至多 O(k) 次空间复杂度O(n)。其中 n 为节点数k 为滑窗大小。解法四二分搜索窗口左边界O(n) / O(n k)直觉解法三需要先定位插入点再向两侧扩张而解法四更进一步直接二分搜索长度为 k 的连续窗口的最优左边界。因为答案是一个连续子数组只需确定它的起点left。判断标准是对任意候选起点mid比较窗口左端arr[mid]与若窗口右移一位会新增的arr[mid k]——若后者离 target 更近说明窗口整体右移更优否则保持左移。算法步骤中序遍历得到升序数组arr二分搜索窗口左边界搜索范围是索引0到n - k对每个中点mid比较arr[mid k]与arr[mid]的距离若mid k处更近则窗口向右收缩left mid 1否则向左收缩right mid返回从最终左边界开始、长度为 k 的子数组。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, arr): if not node: return dfs(node.left, arr) arr.append(node.val) dfs(node.right, arr) arr [] dfs(root, arr) left 0 right len(arr) - k while left right: mid (left right) // 2 if abs(target - arr[mid k]) abs(target - arr[mid]): left mid 1 else: right mid return arr[left:left k]正确性直觉在单调递增的arr上abs(target - arr[i])关于i先递减后递增V 形。若arr[mid k]比arr[mid]更近说明 V 形谷底在mid右侧最优窗口左边界必大于mid反之谷底在mid处或左侧收缩右边界。这与经典寻找山谷二分完全同构。语言实现要点C 使用lower_bound(arr.begin(), arr.end(), target)定位插入点后再进入窗口二分Java 直接以0与arr.size() - k为搜索区间Rust 使用arr.partition_point(|x| (x as f64) target)求出插入位置再执行同样的窗口二分原文档标注该解法在 Java 中时间复杂度为O(n)中序遍历为主二分仅 log n 次比较在 Python 中切片arr[left:left k]额外复制 k 个元素因此记作O(n k)。复杂度分析时间复杂度O(n)Java/ O(n k)Python其中 n 为节点数、k 为返回元素个数空间复杂度O(n)存放有序数组。解法五中序遍历 双端队列Deque构建窗口O(n)直觉解法三、四都依赖先完整中序收集再处理解法五把两者合二为一在遍历的同时维护一个容量为 k 的双端队列。由于中序访问顺序就是升序队列前端始终是当前窗口的最小值最早加入、后端是最大值最新加入。当队列超过 k 个元素时比较首尾元素的距离淘汰距离更远的那一端。更关键的是一旦发现队首元素离 target 更近或相等由于后续访问的值只会更大、离 target 更远可以提前终止右子树遍历避免无谓的访问。算法步骤中序遍历整棵树用双端队列维护当前候选窗口每访问一个节点将其值从队尾入队若队列大小超过 k比较队首与队尾到 target 的距离——若队首更近或相等移除队尾并停止遍历右子树否则移除队首并继续遍历结束队列中即为答案。代码实现class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: def dfs(node, queue): if not node: return dfs(node.left, queue) queue.append(node.val) if len(queue) k: if (abs(target - queue[0]) abs(target - queue[-1])): queue.pop() return else: queue.popleft() dfs(node.right, queue) queue deque() dfs(root, queue) return list(queue)语言实现要点Java 使用DequeInteger queue new LinkedList()通过peekFirst()/peekLast()读端、removeFirst()/removeLast()淘汰C 用dequeintfront()/back()读取、pop_front()/pop_back()淘汰注意这里的return是函数级返回用于剪掉整棵右子树Go 用切片模拟双端队列queue queue[1:]弹出队首、queue queue[:len(queue)-1]弹出队尾Rust 使用VecDequei32与pop_front()/pop_back()语义与 Python 完全一致。复杂度分析时间复杂度O(n)每个节点至多入队一次且多数情况下能提前剪枝空间复杂度O(n k)队列容量 k递归栈最坏 O(n)。其中 n 为节点数k 为返回元素个数。五种解法复杂度对比解法核心思路时间复杂度空间复杂度适用场景1. 自定义比较器排序DFS 收集 全量排序O(n log n)O(n)代码最简适合小规模数据与面试热身2. 大小为 k 的最大堆遍历中维护 Top-KO(n log k)O(n k)不想依赖中序有序性时的通用方案3. 中序遍历 双指针二分定位 两侧扩张O(n k)O(n)充分利用 BST 有序性思路直观4. 二分搜索左边界直接二分窗口起点O(n) / O(n k)O(n)在有序数组上把问题收敛为一次二分5. 中序遍历 Deque遍历中动态维护窗口O(n)O(n k)兼顾时间最优与提前剪枝工程上最优雅n 为树中节点数k 为需要返回的最接近值个数。当树高度不平衡时解法二、五的递归栈深度会退化到 O(n)。常见陷阱Common Pitfalls1. 未利用 BST 性质用通用遍历 全量排序虽然正确却丢失了 BST 特有的 O(n k) 优化空间。中序遍历得到有序数组是本题由 O(n log n) 跃升到 O(n) 的关键任何不使用该性质的方案都值得重新审视。2. 二分搜索中的离一错误Off-by-One用二分定位插入点时插入点可能落在索引 0 或 n 处导致左指针初始化为 -1 或右指针越界# 错误可能产生索引 -1 访问 left bisect_left(arr, target) - 1 # 若 target 小于所有元素left -1 # 必须先判断left 0 时直接访问 arr[left] 会越界解法三的 C/JavaScript/Go 实现均对此做了显式分支处理left 0时只取右侧、right arr.size()时只取左侧。3. 堆类型选错用成最小堆用堆维护 k 个最近值时必须用最大堆来淘汰距离最远的元素。若误用最小堆弹出的反而是距离最近的元素结果完全错误# 错误最小堆会淘汰最近的值 heappush(heap, (abs(node.val - target), node.val)) # 正确最大堆距离取负淘汰最远的值 heappush(heap, (-abs(node.val - target), node.val))4. 相等距离的决胜处理不正确当两个值与 target 距离相等时按题目要求应返回较小值。Python 解法一通过key lambda x: (abs(x - target), x)的元组排序天然处理了决胜其余解法在与的边界语义上需要仔细核对否则在对称输入如 target 恰为两数中点时可能返回错误集合。5. 双指针提前停止、漏掉另一侧在滑动窗口解法中若某一侧指针先越界就立刻停止收集会漏掉另一侧本应入选的元素。正确做法是一侧越界后继续从另一侧单调取数直到集满 k 个解法三各语言实现中均有体现。延伸阅读本题的单值版本返回 1 个最接近值详见 closest-binary-search-tree-value.md其中包含递归中序 线性扫描、迭代中序提前终止O(k)、以及沿单条路径二分O(H)三种递进思路是理解本题由找 1 个推广到找 k 个的最佳铺垫本文完整的多语言实现Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust均收录于 closest-binary-search-tree-value-ii.md仓库根目录 README.md 维护了全部题目的多语言覆盖率总表可按语言目录如python/、cpp/、go/、rust/继续检索相邻的 BST 题目源码。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考