最近在复盘一道老题Closest K Values in BST。我必须说这道题给我留下的印象比很多 hard 题都深。原因不是它难而是它让我重新审视了一个很常见的思维惯性——刷算法题刷久了人很容易把“解决问题”等同于“遍历所有可能”。BST 找离 target 最近的 k 个值第一反应当然是中序遍历转有序数组然后滑窗处理。这个方案没错但它没有用上 BST 真正的优势。后来我想明白一件事最近的不一定靠遍历出来更多时候是靠“定位”和“剪枝”出来的。这篇文章想把这题的完整思考链、两种方案的实现细节、以及背后更通用的算法思路都聊透希望对正在啃二叉树和搜索类题目的朋友有实际帮助。1. 题目本身的“欺骗性”看起来只有遍历一条路1.1 先把 Closest K Values in BST 翻译成人话题目形式上很简单给一棵二叉搜索树、一个目标值 target、一个正整数 k要求返回 BST 中所有节点值里离 target 数值距离最近的 k 个值。比如 target 3.8树里有 1、3、5、7、9 这些值算距离的话 |3 - 3.8| 0.8|5 - 3.8| 1.2所以最近的 k2 个值就是 3 和 5。表面是“找最近”但它考的不是搜索也不是排序而是你对二叉搜索树性质的利用程度。BST 的核心价值就是有序性中序遍历能得到升序序列任意节点的左子树都比它小、右子树都比它大并且可以根据 target 快速判断去哪个子树找。如果看不到这层题目就退化成“给你一棵树你遍历它吧”那 BST 和普通二叉树就没有区别了。1.2 为什么第一反应一定是中序遍历绝大多数人包括我第一次看到这题第一反应就是中序遍历整个 BST得到一个有序数组然后在有序数组上找离 target 最近的 k 个数。这个思路有天然的合理性BST 自带全序中序遍历把树“展开”成一个升序数组后找最近 k 个值就变成一个纯数组问题。在有序数组里可以二分找到 target 的插入位置然后从那个位置向左右两侧扩散每次比较左指针和右指针指向的值谁离 target 更近谁近就收谁。整个流程清晰、正确、可证明。LeetCode 272 原题其实还有个温和的版本要求返回这 k 个值不限顺序。那中序 窗口就是最顺手的解法。我最早写的时候也是这么干的一次 AC心里还挺爽。但后来看复杂度越看越别扭。1.3 中序方案能过但复杂度在哪里吃亏中序 数组方案的复杂度分两段中序遍历整棵树O(n)n 是节点总数。有序数组上找最近 k 个如果用二分定位 双指针扩散这部分只有 O(log n k)。问题在于第二部分虽然很省但第一部分把整棵树都过了一遍。如果树有 100 万个节点而 k 只是 3你要为了找 3 个数把 100 万个节点全部访问一遍这在数据量小的时候无所谓数据量一上来就很痛。你可以反驳BST 又不会太大。这在面试题里成立但在工程场景不一定。比如一个用户行为日志索引树、一个地理位置索引、一个自动补全词典节点轻松到百万级每次请求只取 top-k却要全量遍历建数组那服务基本没法做。退一步说即使不讨论工程单从算法训练的视角看这道题放在“二叉搜索树”这个标签下出题人显然希望你能利用 BST 的搜索方向性而不是无差别遍历。如果只把 BST 当中序数组来用那 AVL、红黑树、B 树这些结构的存在意义就被浪费了大半。所以从解出题到解好题中间还差一层。2. 换个问法“最近”不应该靠全量排序而应该靠定位2.1 有序数据上找最近值本质是“定位 扩散”回头看问题的本质BST 是一棵有序树你要找的不再是“整棵树的统计量”而是“某个目标附近的一小块区域”。这里可以类比现实中的地图找店你在一条商业街上要找离当前位置最近的 3 家奶茶店。你不会从街头走到街尾把每一家店都看一眼才得出结论而是先确定自己在街上的位置然后往左看一眼、往右看一眼哪边近就往哪边走交替扩展直到找够 3 家。BST 也是同理。中序遍历序列相当于一条“街道”而二叉搜索树的搜索路径就是“导航定位”。你完全不需要把整条街逛完只需要定位沿着树从根往下走找到 target 在树中的“插入位置”附近。扩散从那个位置开始交替向“前驱”和“后继”两个方向探索每次取距离更近的一侧。2.2 两个栈给“前驱”和“后继”分别建游标要在 BST 上实现“向左扩散”和“向右扩散”最自然的数据结构是双栈。这里需要先理解 BST 中的“前驱”和“后继”是什么意思某个值的前驱中序遍历序列中排在它前面那个值也就是“比 target 小的值里最大的那个”。某个值的后继中序遍历序列中排在它后面那个值也就是“比 target 大的值里最小的那个”。从 target 附近开始找最近 k 个值本质上就是不断比较“当前最近的前驱”和“当前最近的后继”谁离 target 更近就把谁取出来取完后继续向该方向推进。但问题是BST 的节点没有 parent 指针你无法从一个节点直接跳到它的前驱或后继。所以需要借助栈来“记住”还没有被探索完的候选节点。设计思路是这样的predecessorStack存放“还有可能成为前驱”的候选节点栈顶是当前最接近 target 的那个前驱候选。successorStack存放“还有可能成为后继”的候选节点栈顶是当前最接近 target 的那个后继候选。每次需要拿下一个数时只需要看两个栈的栈顶哪个离 target 更近就弹出哪个。这个设计很像给中序遍历装了两个“迭代器”一个向前走一个向后走。2.3 沿查找路径分配候选节点的过程关键问题来了初始时怎么把根节点路径上的节点正确分配到两个栈里我们从根节点开始沿 BST 的搜索路径往下走规则只有两条如果node.val target说明目标在 node 的右边或者就在 node 本身上。node 本身有资格成为“前驱”因为它小于等于 target同时它的右子树里可能有更接近 target 但依然小于等于 target 的节点。所以把 node 压入predecessorStack然后继续往右走。如果node.val target说明目标在 node 的左边。node 本身有资格成为“后继”因为它大于 target同时它的左子树里可能有更接近 target 但依然大于 target 的节点。所以把 node 压入successorStack然后继续往左走。这个过程一直持续到 node 为空。这样做的结果很有趣整条搜索路径上的每个节点都被分配到了它对应的栈里而两个栈的栈顶恰好就是整棵树中“小于等于 target 的最大值”和“大于 target 的最小值”这两个最核心的位置。这就是扩散的起点。我举个具体例子。假设 BST 是这样一棵树10 / \ 5 15 / \ / \ 2 7 12 20target 8k 3。从根节点 10 开始10 8压入 successorStack往左走。 到 55 8压入 predecessorStack往右走。 到 77 8压入 predecessorStack往右走。 到空。两个栈的状态是predecessorStack [5, 7]栈顶 7离 target 距离 1successorStack [10]栈顶 10离 target 距离 2第一次取数比较栈顶7 离 8 更近pop 7。取完之后需要补充 7 的“左边区域”——因为 7 的左子树里可能有比 5 更大但依然小于 7 且接近 8 的节点。这里 7 没有左子树所以不补充。此时 predecessorStack 变成 [5]successorStack 还是 [10]。继续比较5 的距离是 310 的距离是 2取 10。再补充 10 的左子树里的候选节点10 的左子树根是 5但 5 已经在 predecessorStack 中了不需要重复处理。到这里输出 [7, 10, 5]也就是离 8 最近的三个值是 7、10、5。如果用任意顺序返回没问题。注意这个分配过程非常关键也是面试时最容易被问到的点为什么搜索路径上往左走时压 successor、往右走时压 predecessor答案就是因为你往哪个方向走就说明哪个方向的边界已经被进一步缩小了而当前节点本身还在另一个方向的候选范围内先把它存下来后面才有机会取到。3. 双栈导航的完整实现与复杂度分析3.1 核心代码Python 版直接给出可运行的实现。为了方便阅读我把初始化栈和迭代前驱/后继的逻辑拆开写清楚。class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: pred_stack [] succ_stack [] # 1. 沿查找路径初始化两个候选栈 node root while node: if node.val target: pred_stack.append(node) # 当前节点作为“前驱”候选 node node.right # 更大值在右子树继续逼近 else: succ_stack.append(node) # 当前节点作为“后继”候选 node node.left # 更小值在左子树继续逼近 result [] # 2. 每次比较两个栈顶谁更近就取谁 while len(result) k: if not pred_stack: result.append(self._next_successor(succ_stack)) elif not succ_stack: result.append(self._next_predecessor(pred_stack)) else: if abs(succ_stack[-1].val - target) abs(pred_stack[-1].val - target): result.append(self._next_successor(succ_stack)) else: result.append(self._next_predecessor(pred_stack)) return result def _next_predecessor(self, pred_stack: List[TreeNode]) - int: 取出当前最大前驱并补充该节点的左子树右链作为新的前驱候选 cur pred_stack.pop() val cur.val nxt cur.left while nxt: pred_stack.append(nxt) nxt nxt.right return val def _next_successor(self, succ_stack: List[TreeNode]) - int: 取出当前最小后继并补充该节点的右子树左链作为新的后继候选 cur succ_stack.pop() val cur.val nxt cur.right while nxt: succ_stack.append(nxt) nxt nxt.left return val这段代码的核心就两个函数_next_predecessor和_next_successor。理解了这两个函数整个算法就理解了一半。3.2 前驱/后继游标的机制为什么 pop 之后要补链很多人看到_next_predecessor里 pop 完还要把cur.left一路向右压栈会觉得奇怪我明明只是取一个数为什么还要额外操作原因在于BST 中序遍历的“上一个”并不是简单的树的左孩子。假设当前弹出的节点是 curcur 是整个 BST 中“还没被取走的前驱里最大的那一个”。那么下一个前驱候选是谁是 cur 的左子树中最大的那个值也就是cur.left开始一路向右走到头的那个节点。举个例子8 / \ 3 10 / \ 1 6 / \ 4 7如果 target 9初始化时predecessorStack会存入 8 和它的右链这里 8 的右孩子是 10但 10 9 会被放到 successor 栈。假设我们从 predecessor 栈中取出了 8那下一个要取的前驱就是 8 的左子树中最大的节点也就是从 3 开始往右走到头的 7。如果不把cur.left的右链压栈等下一次比较前驱时你就不知道还有 7 这个节点存在也就无法正确按从大到小的顺序输出前驱序列。补链操作本质上是在维护一个方向上的有序迭代器。这和中序遍历迭代写法的栈原理完全一致只是这里同时维护了两个方向。3.3 复杂度证明为什么是 O(hk) 而不是 O(n)这个方案的时间复杂度非常有意思它不是 O(n)。拆开看初始化两个栈从根一路走到空节点最多走 h 步h 是树高所以是 O(h)。取数阶段每次取一个数会做一次 pop 和一次补链。补链过程中每个节点最多被压入栈一次、弹出栈一次整个过程在 k 次取数内总共涉及的节点数不超过 k。所以这阶段是 O(k)。总时间复杂度O(h k)。最坏情况下树退化成链h 可能等于 n那 O(h k) 会退化成 O(n)。但即便如此它仍然有一个优势如果树是平衡的h 远小于 n这个优势会被放大到极致。100 万节点的平衡树树高只有 20 左右取 k10 个最近值时只需访问 30 个左右的节点。相比之下中序遍历方案要访问 100 万次节点。空间复杂度两个栈中各存一条搜索路径最坏情况下 O(h k)平衡树场景下同样非常有限。这也解释了标题里“最近的不一定是遍历出来的”——当你利用好有序结构的分布性质时很多问题的答案只藏在很小的一块区域内不需要到处跑。复杂度从 O(n) 到 O(hk)看似只是符号变化但在数据量大时是本质差别。4. 容易翻车的细节和边界条件4.1 k 大于节点总数、target 不在树中、距离相等这三个是高频边界场景一个一个说。k 大于节点总数题目一般会保证 k 不超过节点数但实际面试或者自测时不一定。双栈解法里如果 k n取完所有节点后两个栈都为空循环体里pred_stack和succ_stack同时为空会导致错误。稳妥做法是提前数一下节点数或者循环条件加一个while len(result) k and (pred_stack or succ_stack):否则直接 break。target 不在树中这个场景其实完全不需要担心双栈方案天然支持。初始化栈时就是沿着搜索路径走到空如果 target 值落在某两个节点之间那两个节点会分别出现在 pred_stack 和 succ_stack 的栈顶。比如上面例子中 target 8树中没有 8但 7 和 10 依然被正确找出来。这个方案本身就是为“寻找插入位置”设计的。距离相等比如 target 6前驱是 5后继是 7|5-6| 和 |7-6| 相等取哪个都算正确。但代码里如果用了和的边界要保证不会取到无穷循环。我的建议是相等时统一取前驱或统一取后继顺序无所谓但要保证不会两边都跳过。实现里用abs(succ - target) abs(pred - target)时相等时走 else 取前驱行为可以预测。4.2 树退化成链表时的表现BST 并不总是平衡的。如果你碰上的是极端不平衡树比如插入了有序数据导致树变成一条左链或右链树高 h n那 O(hk) 会退化成 O(nk)。这时候双栈方案相对中序遍历还有没有优势有但不多。优势在于它不需要存储完整的 n 个元素数组空间上更省劣势是时间复杂度退化了。所以一点实话实说双栈方案在平衡 BST 上是最优的但如果你面对的是一棵已经严重失衡的树先平衡它再谈高效查找。工程中要避免这种情况比如用红黑树、AVL算法题中如果专门给退化树卡你那目的就是考你对复杂度的敏感度你最好把两种方案的取舍讲清楚。4.3 返回顺序的坑题目要不要有序结果这个点特别容易踩。LeetCode 272 原题返回的 k 个数是任意顺序所以双栈方案直接从近到远输出没有任何问题。但如果题目要求“按 BST 中序遍历顺序输出这 k 个数”那就不一样了。比如 target 8最近三个值是 7、10、5双栈方案返回[7, 10, 5]可如果要求升序应该是[5, 7, 10]。处理方式很简单最后对结果做一次排序时间复杂度 O(k log k)。k 通常很小完全可接受。补充一句如果想避免最后排序可以在双栈取数时先把值收进一个数组取满 k 个后再排序。或者用中序窗口法天然保证顺序。选哪种取决于题目要求不要在没看清题的情况下默认任意顺序直接交。4.4 和 Morris 遍历方案的取舍有些同学会提出 Morris 中序遍历说它能做到 O(1) 空间。对Morris 遍历确实可以用 O(1) 额外空间完成中序遍历但它在遍历过程中会临时修改树的指针结构遍历完再恢复。这在算法竞赛和面试中可以用但在工程上不太被接受——并发场景下改树结构是个灾难而且恢复逻辑一旦出错整棵树就废了。我做技术选型时有个原则如果两种解法时间同级优先选不破坏数据结构的如果有空间换时间优先选可读性好的。双栈方案虽然空间比 Morris 多但它不修改树、可读性高、实现稳是最适合实际写进代码库的方案。下表把这三种主流方案放在一起对比方案时间复杂度空间复杂度是否修改树适用场景中序数组 二分扩散O(n log n k)O(n)否小树 / 需要全序结果中序窗口 双端队列O(n)O(h k)否k 接近 n / 一次遍历搞定双栈导航O(h k)O(h k)否大树 小 k / 多次查询Morris 中序O(n)O(1)是对空间极端敏感且允许改树大多数情况下我推荐双栈方案。5. 从“遍历”到“导航”算法的节制感5.1 面试中的展示顺序先给保守解再给克制解如果你是在面试里遇到这道题我的建议是别一上来就写双栈。不是双栈不好而是面试官需要看到你的思维过程。更合适的节奏是先聊中序 数组方案说明这是“利用有序性”的暴力解复杂度 O(n)。再顺着“BST 搜索路径可以定位”这个点提出双栈导航复杂度降到 O(hk)。最后补一句如果树不平衡可能退化所以实际中要配合平衡树使用。这样展示的不是“你背过最优解”而是“你有能力从基础解出发分析瓶颈再设计更优方案”。这两个层次在面试中的差距比 AC 一道题大得多。5.2 工程里的“按需推进”从游标到懒加载双栈方案的本质是一种按需计算或者叫 lazy evaluation。它和好几类工程实践是同构的数据库的游标分页不一次性查出所有数据而是维护一个游标位置按需拉下一页。这就是“不遍历全表只沿着索引定位扩散”。搜索引擎的 top-k不会把所有文档相关性都算完再排而是用一个大小为 k 的堆维护当前 top-k遍历过程中不断淘汰最差的。日志检索在有序时间戳索引里找某个时间段附近的记录用二分定位起点再朝两边拉取而不是全量扫描。懒加载流处理Java 的 Stream、Python 的 generator、Kafka 的消费者 offset本质上都是“用游标维护状态按需获取下一批”避免一次性加载全部数据。这些场景的共同点就是数据全集很大但答案只集中在一个很小的局部。在这种情况下全量遍历是低效的你需要的是“定位 按需扩展”。5.3 什么时候该节制什么时候该老老实实遍历当然不是所有情况都适合“克制”。如果数据规模本来就小比如只有几十个节点写双栈反而增加心智负担中序 数组最直接清晰。如果 k 接近 n那不管用什么方案最终都要访问大量节点中序遍历一次搞定反而没有额外开销。如果结果要求严格有序且树结构不稳定老老实实中序数组可能更安全。“节制感”不是在所有情况下都选最复杂的方案而是判断清楚问题的规模和数据结构的性质选择在时间和空间上真正合适的做法。二叉搜索树之所以比无序二叉树有价值就是因为它允许你“不看完所有节点就做出判断”。当你面对一个带有有序性质的数据结构时先问问自己答案真的需要全局信息吗如果只需要局部那就没必要遍历全量。就这道题来说“局部”由 target 的位置决定由两个栈维护的前驱/后继边界圈定。利用好这个边界就掌握了这个算法的灵魂。5.4 一点个人体会最后说点题外话。我早期刷题特别喜欢“稳妥解”能用遍历解决的绝不搞花活因为遍历方案最简单、最容易证明正确。但工作几年后处理的数据量从几千涨到几百万才发现正确但不高效的解法在真实系统里往往是不可用解法。你不会想在一个百万节点的索引上做一次全量遍历去回答一个 top-10 查询。那道题之后我养成了一个习惯每次看到一个有序数据结构先条件反射地追问一句——这里能不能不遍历完这个追问帮我解决过很多真实问题也让我对算法的理解从“知道”变成了“会选”。希望这篇笔记也能给你同样的启发。
最近在复盘一道老题Closest K Values in BST。我必须说这道题给我留下的印象比很多 hard 题都深。原因不是它难而是它让我重新审视了一个很常见的思维惯性——刷算法题刷久了人很容易把“解决问题”等同于“遍历所有可能”。BST 找离 target 最近的 k 个值第一反应当然是中序遍历转有序数组然后滑窗处理。这个方案没错但它没有用上 BST 真正的优势。后来我想明白一件事最近的不一定靠遍历出来更多时候是靠“定位”和“剪枝”出来的。这篇文章想把这题的完整思考链、两种方案的实现细节、以及背后更通用的算法思路都聊透希望对正在啃二叉树和搜索类题目的朋友有实际帮助。1. 题目本身的“欺骗性”看起来只有遍历一条路1.1 先把 Closest K Values in BST 翻译成人话题目形式上很简单给一棵二叉搜索树、一个目标值 target、一个正整数 k要求返回 BST 中所有节点值里离 target 数值距离最近的 k 个值。比如 target 3.8树里有 1、3、5、7、9 这些值算距离的话 |3 - 3.8| 0.8|5 - 3.8| 1.2所以最近的 k2 个值就是 3 和 5。表面是“找最近”但它考的不是搜索也不是排序而是你对二叉搜索树性质的利用程度。BST 的核心价值就是有序性中序遍历能得到升序序列任意节点的左子树都比它小、右子树都比它大并且可以根据 target 快速判断去哪个子树找。如果看不到这层题目就退化成“给你一棵树你遍历它吧”那 BST 和普通二叉树就没有区别了。1.2 为什么第一反应一定是中序遍历绝大多数人包括我第一次看到这题第一反应就是中序遍历整个 BST得到一个有序数组然后在有序数组上找离 target 最近的 k 个数。这个思路有天然的合理性BST 自带全序中序遍历把树“展开”成一个升序数组后找最近 k 个值就变成一个纯数组问题。在有序数组里可以二分找到 target 的插入位置然后从那个位置向左右两侧扩散每次比较左指针和右指针指向的值谁离 target 更近谁近就收谁。整个流程清晰、正确、可证明。LeetCode 272 原题其实还有个温和的版本要求返回这 k 个值不限顺序。那中序 窗口就是最顺手的解法。我最早写的时候也是这么干的一次 AC心里还挺爽。但后来看复杂度越看越别扭。1.3 中序方案能过但复杂度在哪里吃亏中序 数组方案的复杂度分两段中序遍历整棵树O(n)n 是节点总数。有序数组上找最近 k 个如果用二分定位 双指针扩散这部分只有 O(log n k)。问题在于第二部分虽然很省但第一部分把整棵树都过了一遍。如果树有 100 万个节点而 k 只是 3你要为了找 3 个数把 100 万个节点全部访问一遍这在数据量小的时候无所谓数据量一上来就很痛。你可以反驳BST 又不会太大。这在面试题里成立但在工程场景不一定。比如一个用户行为日志索引树、一个地理位置索引、一个自动补全词典节点轻松到百万级每次请求只取 top-k却要全量遍历建数组那服务基本没法做。退一步说即使不讨论工程单从算法训练的视角看这道题放在“二叉搜索树”这个标签下出题人显然希望你能利用 BST 的搜索方向性而不是无差别遍历。如果只把 BST 当中序数组来用那 AVL、红黑树、B 树这些结构的存在意义就被浪费了大半。所以从解出题到解好题中间还差一层。2. 换个问法“最近”不应该靠全量排序而应该靠定位2.1 有序数据上找最近值本质是“定位 扩散”回头看问题的本质BST 是一棵有序树你要找的不再是“整棵树的统计量”而是“某个目标附近的一小块区域”。这里可以类比现实中的地图找店你在一条商业街上要找离当前位置最近的 3 家奶茶店。你不会从街头走到街尾把每一家店都看一眼才得出结论而是先确定自己在街上的位置然后往左看一眼、往右看一眼哪边近就往哪边走交替扩展直到找够 3 家。BST 也是同理。中序遍历序列相当于一条“街道”而二叉搜索树的搜索路径就是“导航定位”。你完全不需要把整条街逛完只需要定位沿着树从根往下走找到 target 在树中的“插入位置”附近。扩散从那个位置开始交替向“前驱”和“后继”两个方向探索每次取距离更近的一侧。2.2 两个栈给“前驱”和“后继”分别建游标要在 BST 上实现“向左扩散”和“向右扩散”最自然的数据结构是双栈。这里需要先理解 BST 中的“前驱”和“后继”是什么意思某个值的前驱中序遍历序列中排在它前面那个值也就是“比 target 小的值里最大的那个”。某个值的后继中序遍历序列中排在它后面那个值也就是“比 target 大的值里最小的那个”。从 target 附近开始找最近 k 个值本质上就是不断比较“当前最近的前驱”和“当前最近的后继”谁离 target 更近就把谁取出来取完后继续向该方向推进。但问题是BST 的节点没有 parent 指针你无法从一个节点直接跳到它的前驱或后继。所以需要借助栈来“记住”还没有被探索完的候选节点。设计思路是这样的predecessorStack存放“还有可能成为前驱”的候选节点栈顶是当前最接近 target 的那个前驱候选。successorStack存放“还有可能成为后继”的候选节点栈顶是当前最接近 target 的那个后继候选。每次需要拿下一个数时只需要看两个栈的栈顶哪个离 target 更近就弹出哪个。这个设计很像给中序遍历装了两个“迭代器”一个向前走一个向后走。2.3 沿查找路径分配候选节点的过程关键问题来了初始时怎么把根节点路径上的节点正确分配到两个栈里我们从根节点开始沿 BST 的搜索路径往下走规则只有两条如果node.val target说明目标在 node 的右边或者就在 node 本身上。node 本身有资格成为“前驱”因为它小于等于 target同时它的右子树里可能有更接近 target 但依然小于等于 target 的节点。所以把 node 压入predecessorStack然后继续往右走。如果node.val target说明目标在 node 的左边。node 本身有资格成为“后继”因为它大于 target同时它的左子树里可能有更接近 target 但依然大于 target 的节点。所以把 node 压入successorStack然后继续往左走。这个过程一直持续到 node 为空。这样做的结果很有趣整条搜索路径上的每个节点都被分配到了它对应的栈里而两个栈的栈顶恰好就是整棵树中“小于等于 target 的最大值”和“大于 target 的最小值”这两个最核心的位置。这就是扩散的起点。我举个具体例子。假设 BST 是这样一棵树10 / \ 5 15 / \ / \ 2 7 12 20target 8k 3。从根节点 10 开始10 8压入 successorStack往左走。 到 55 8压入 predecessorStack往右走。 到 77 8压入 predecessorStack往右走。 到空。两个栈的状态是predecessorStack [5, 7]栈顶 7离 target 距离 1successorStack [10]栈顶 10离 target 距离 2第一次取数比较栈顶7 离 8 更近pop 7。取完之后需要补充 7 的“左边区域”——因为 7 的左子树里可能有比 5 更大但依然小于 7 且接近 8 的节点。这里 7 没有左子树所以不补充。此时 predecessorStack 变成 [5]successorStack 还是 [10]。继续比较5 的距离是 310 的距离是 2取 10。再补充 10 的左子树里的候选节点10 的左子树根是 5但 5 已经在 predecessorStack 中了不需要重复处理。到这里输出 [7, 10, 5]也就是离 8 最近的三个值是 7、10、5。如果用任意顺序返回没问题。注意这个分配过程非常关键也是面试时最容易被问到的点为什么搜索路径上往左走时压 successor、往右走时压 predecessor答案就是因为你往哪个方向走就说明哪个方向的边界已经被进一步缩小了而当前节点本身还在另一个方向的候选范围内先把它存下来后面才有机会取到。3. 双栈导航的完整实现与复杂度分析3.1 核心代码Python 版直接给出可运行的实现。为了方便阅读我把初始化栈和迭代前驱/后继的逻辑拆开写清楚。class Solution: def closestKValues(self, root: TreeNode, target: float, k: int) - List[int]: pred_stack [] succ_stack [] # 1. 沿查找路径初始化两个候选栈 node root while node: if node.val target: pred_stack.append(node) # 当前节点作为“前驱”候选 node node.right # 更大值在右子树继续逼近 else: succ_stack.append(node) # 当前节点作为“后继”候选 node node.left # 更小值在左子树继续逼近 result [] # 2. 每次比较两个栈顶谁更近就取谁 while len(result) k: if not pred_stack: result.append(self._next_successor(succ_stack)) elif not succ_stack: result.append(self._next_predecessor(pred_stack)) else: if abs(succ_stack[-1].val - target) abs(pred_stack[-1].val - target): result.append(self._next_successor(succ_stack)) else: result.append(self._next_predecessor(pred_stack)) return result def _next_predecessor(self, pred_stack: List[TreeNode]) - int: 取出当前最大前驱并补充该节点的左子树右链作为新的前驱候选 cur pred_stack.pop() val cur.val nxt cur.left while nxt: pred_stack.append(nxt) nxt nxt.right return val def _next_successor(self, succ_stack: List[TreeNode]) - int: 取出当前最小后继并补充该节点的右子树左链作为新的后继候选 cur succ_stack.pop() val cur.val nxt cur.right while nxt: succ_stack.append(nxt) nxt nxt.left return val这段代码的核心就两个函数_next_predecessor和_next_successor。理解了这两个函数整个算法就理解了一半。3.2 前驱/后继游标的机制为什么 pop 之后要补链很多人看到_next_predecessor里 pop 完还要把cur.left一路向右压栈会觉得奇怪我明明只是取一个数为什么还要额外操作原因在于BST 中序遍历的“上一个”并不是简单的树的左孩子。假设当前弹出的节点是 curcur 是整个 BST 中“还没被取走的前驱里最大的那一个”。那么下一个前驱候选是谁是 cur 的左子树中最大的那个值也就是cur.left开始一路向右走到头的那个节点。举个例子8 / \ 3 10 / \ 1 6 / \ 4 7如果 target 9初始化时predecessorStack会存入 8 和它的右链这里 8 的右孩子是 10但 10 9 会被放到 successor 栈。假设我们从 predecessor 栈中取出了 8那下一个要取的前驱就是 8 的左子树中最大的节点也就是从 3 开始往右走到头的 7。如果不把cur.left的右链压栈等下一次比较前驱时你就不知道还有 7 这个节点存在也就无法正确按从大到小的顺序输出前驱序列。补链操作本质上是在维护一个方向上的有序迭代器。这和中序遍历迭代写法的栈原理完全一致只是这里同时维护了两个方向。3.3 复杂度证明为什么是 O(hk) 而不是 O(n)这个方案的时间复杂度非常有意思它不是 O(n)。拆开看初始化两个栈从根一路走到空节点最多走 h 步h 是树高所以是 O(h)。取数阶段每次取一个数会做一次 pop 和一次补链。补链过程中每个节点最多被压入栈一次、弹出栈一次整个过程在 k 次取数内总共涉及的节点数不超过 k。所以这阶段是 O(k)。总时间复杂度O(h k)。最坏情况下树退化成链h 可能等于 n那 O(h k) 会退化成 O(n)。但即便如此它仍然有一个优势如果树是平衡的h 远小于 n这个优势会被放大到极致。100 万节点的平衡树树高只有 20 左右取 k10 个最近值时只需访问 30 个左右的节点。相比之下中序遍历方案要访问 100 万次节点。空间复杂度两个栈中各存一条搜索路径最坏情况下 O(h k)平衡树场景下同样非常有限。这也解释了标题里“最近的不一定是遍历出来的”——当你利用好有序结构的分布性质时很多问题的答案只藏在很小的一块区域内不需要到处跑。复杂度从 O(n) 到 O(hk)看似只是符号变化但在数据量大时是本质差别。4. 容易翻车的细节和边界条件4.1 k 大于节点总数、target 不在树中、距离相等这三个是高频边界场景一个一个说。k 大于节点总数题目一般会保证 k 不超过节点数但实际面试或者自测时不一定。双栈解法里如果 k n取完所有节点后两个栈都为空循环体里pred_stack和succ_stack同时为空会导致错误。稳妥做法是提前数一下节点数或者循环条件加一个while len(result) k and (pred_stack or succ_stack):否则直接 break。target 不在树中这个场景其实完全不需要担心双栈方案天然支持。初始化栈时就是沿着搜索路径走到空如果 target 值落在某两个节点之间那两个节点会分别出现在 pred_stack 和 succ_stack 的栈顶。比如上面例子中 target 8树中没有 8但 7 和 10 依然被正确找出来。这个方案本身就是为“寻找插入位置”设计的。距离相等比如 target 6前驱是 5后继是 7|5-6| 和 |7-6| 相等取哪个都算正确。但代码里如果用了和的边界要保证不会取到无穷循环。我的建议是相等时统一取前驱或统一取后继顺序无所谓但要保证不会两边都跳过。实现里用abs(succ - target) abs(pred - target)时相等时走 else 取前驱行为可以预测。4.2 树退化成链表时的表现BST 并不总是平衡的。如果你碰上的是极端不平衡树比如插入了有序数据导致树变成一条左链或右链树高 h n那 O(hk) 会退化成 O(nk)。这时候双栈方案相对中序遍历还有没有优势有但不多。优势在于它不需要存储完整的 n 个元素数组空间上更省劣势是时间复杂度退化了。所以一点实话实说双栈方案在平衡 BST 上是最优的但如果你面对的是一棵已经严重失衡的树先平衡它再谈高效查找。工程中要避免这种情况比如用红黑树、AVL算法题中如果专门给退化树卡你那目的就是考你对复杂度的敏感度你最好把两种方案的取舍讲清楚。4.3 返回顺序的坑题目要不要有序结果这个点特别容易踩。LeetCode 272 原题返回的 k 个数是任意顺序所以双栈方案直接从近到远输出没有任何问题。但如果题目要求“按 BST 中序遍历顺序输出这 k 个数”那就不一样了。比如 target 8最近三个值是 7、10、5双栈方案返回[7, 10, 5]可如果要求升序应该是[5, 7, 10]。处理方式很简单最后对结果做一次排序时间复杂度 O(k log k)。k 通常很小完全可接受。补充一句如果想避免最后排序可以在双栈取数时先把值收进一个数组取满 k 个后再排序。或者用中序窗口法天然保证顺序。选哪种取决于题目要求不要在没看清题的情况下默认任意顺序直接交。4.4 和 Morris 遍历方案的取舍有些同学会提出 Morris 中序遍历说它能做到 O(1) 空间。对Morris 遍历确实可以用 O(1) 额外空间完成中序遍历但它在遍历过程中会临时修改树的指针结构遍历完再恢复。这在算法竞赛和面试中可以用但在工程上不太被接受——并发场景下改树结构是个灾难而且恢复逻辑一旦出错整棵树就废了。我做技术选型时有个原则如果两种解法时间同级优先选不破坏数据结构的如果有空间换时间优先选可读性好的。双栈方案虽然空间比 Morris 多但它不修改树、可读性高、实现稳是最适合实际写进代码库的方案。下表把这三种主流方案放在一起对比方案时间复杂度空间复杂度是否修改树适用场景中序数组 二分扩散O(n log n k)O(n)否小树 / 需要全序结果中序窗口 双端队列O(n)O(h k)否k 接近 n / 一次遍历搞定双栈导航O(h k)O(h k)否大树 小 k / 多次查询Morris 中序O(n)O(1)是对空间极端敏感且允许改树大多数情况下我推荐双栈方案。5. 从“遍历”到“导航”算法的节制感5.1 面试中的展示顺序先给保守解再给克制解如果你是在面试里遇到这道题我的建议是别一上来就写双栈。不是双栈不好而是面试官需要看到你的思维过程。更合适的节奏是先聊中序 数组方案说明这是“利用有序性”的暴力解复杂度 O(n)。再顺着“BST 搜索路径可以定位”这个点提出双栈导航复杂度降到 O(hk)。最后补一句如果树不平衡可能退化所以实际中要配合平衡树使用。这样展示的不是“你背过最优解”而是“你有能力从基础解出发分析瓶颈再设计更优方案”。这两个层次在面试中的差距比 AC 一道题大得多。5.2 工程里的“按需推进”从游标到懒加载双栈方案的本质是一种按需计算或者叫 lazy evaluation。它和好几类工程实践是同构的数据库的游标分页不一次性查出所有数据而是维护一个游标位置按需拉下一页。这就是“不遍历全表只沿着索引定位扩散”。搜索引擎的 top-k不会把所有文档相关性都算完再排而是用一个大小为 k 的堆维护当前 top-k遍历过程中不断淘汰最差的。日志检索在有序时间戳索引里找某个时间段附近的记录用二分定位起点再朝两边拉取而不是全量扫描。懒加载流处理Java 的 Stream、Python 的 generator、Kafka 的消费者 offset本质上都是“用游标维护状态按需获取下一批”避免一次性加载全部数据。这些场景的共同点就是数据全集很大但答案只集中在一个很小的局部。在这种情况下全量遍历是低效的你需要的是“定位 按需扩展”。5.3 什么时候该节制什么时候该老老实实遍历当然不是所有情况都适合“克制”。如果数据规模本来就小比如只有几十个节点写双栈反而增加心智负担中序 数组最直接清晰。如果 k 接近 n那不管用什么方案最终都要访问大量节点中序遍历一次搞定反而没有额外开销。如果结果要求严格有序且树结构不稳定老老实实中序数组可能更安全。“节制感”不是在所有情况下都选最复杂的方案而是判断清楚问题的规模和数据结构的性质选择在时间和空间上真正合适的做法。二叉搜索树之所以比无序二叉树有价值就是因为它允许你“不看完所有节点就做出判断”。当你面对一个带有有序性质的数据结构时先问问自己答案真的需要全局信息吗如果只需要局部那就没必要遍历全量。就这道题来说“局部”由 target 的位置决定由两个栈维护的前驱/后继边界圈定。利用好这个边界就掌握了这个算法的灵魂。5.4 一点个人体会最后说点题外话。我早期刷题特别喜欢“稳妥解”能用遍历解决的绝不搞花活因为遍历方案最简单、最容易证明正确。但工作几年后处理的数据量从几千涨到几百万才发现正确但不高效的解法在真实系统里往往是不可用解法。你不会想在一个百万节点的索引上做一次全量遍历去回答一个 top-10 查询。那道题之后我养成了一个习惯每次看到一个有序数据结构先条件反射地追问一句——这里能不能不遍历完这个追问帮我解决过很多真实问题也让我对算法的理解从“知道”变成了“会选”。希望这篇笔记也能给你同样的启发。
