LeetCode 230：二叉搜索树第K小元素三种解法与面试详解

LeetCode 230题“二叉搜索树中第k小的元素”是Java面试里出现频率极高的一道题。题目本身不长：给定一棵二叉搜索树（BST）的根节点root，和一个整数k，返回其中第k小的元素。简单说，就是在一个树结构里做一次“排名查询”。

热词里能看到“java面试八股文”、“leetcode题解”这些词条，说明这道题早就是被嚼烂了的面试原题。但真正能一次写对、还能把进阶解法讲清楚的人，其实不多。我面过不少候选人，很多人能背出“中序遍历”四个字，代码却写不利索，要么漏了终止条件，要么没搞懂k是从1开始计数的。所以这篇把这道题的来龙去脉、三种主流解法、复杂度对比，以及面试官最爱的几个追问一次性讲透。

1. 题目拆解与BST中序遍历的核心原理

1.1 二叉搜索树的天然排序特性

二叉搜索树的定义很简洁：左子树所有节点的值都小于根节点，右子树所有节点的值都大于根节点，且左右子树本身也满足这个条件。

这个定义决定了它一个极其重要的性质：中序遍历（左子树 → 根节点 → 右子树）得到的结果一定是一个升序序列。这不是什么高深数学结论，你随手画一棵BST就能验证。根节点的值介于左右子树之间，那先访问完所有比根小的左子树节点，再访问根，最后访问所有比根大的右子树节点，走完自然就是从最小到最大。

这道题能成立的全部依据，就是这一条。第k小的元素，等价于中序遍历序列里下标为k-1的那个元素，也就是中序遍历过程中第k个被访问的节点。

我举个具体例子：一棵BST长这样——

3 / \ 1 4 \ 2

中序遍历走一遍：1 → 2 → 3 → 4。如果k=3，第3小的元素就是3，也就是根节点本身。

这个例子也顺带说明了一个细节：BST的第k小元素不一定在左子树，也不一定在叶子节点，所以“从最左边开始数”是正确思路，但不能想当然地认为答案一定是最左路径上的某个节点。

1.2 为什么这道题是面试高频题

这道题在LeetCode上的热度长期排在前列，不是没有原因的。它综合考察了好几个层面的能力：

• 对树这种数据结构的理解是否扎实
• 是否掌握递归和迭代两种遍历方式
• 对时间复杂度的敏感度
• 面对“进阶要求”时能否想到优化方案

面试官也特别喜欢拿它做引子，往各个方向延伸：问第k大怎么办、问如果树经常被修改怎么办、问不用BST性质怎么做。热词里跟“java面试八股文”、“java面试题”相关的信息很多，这道题就是典型的“看似基础、实则能挖很深”的八股。

从刷题策略上看，这道题也值得反复做三遍以上。第一遍用最简单的递归中序遍历AC，第二遍用迭代中序遍历巩固栈的操作，第三遍再想明白分治计数法和进阶优化的思路。每一遍的收获都不一样。

1.3 暴力解法为什么不可取

很多人拿到题第一反应是：把树里所有节点值都取出来，放到一个数组里排个序，然后取第k个。这个思路没错，但完全没用到BST的排序特性。

这种做法的复杂度是O(n log n)，n是节点总数。排序一遍是O(n log n)，取第k个是O(1)。而直接中序遍历是O(n)，如果提前终止甚至只需要O(h + k)，h是树高。数据量小的时候看不出区别，一旦树里有几十万个节点，排序的时间开销明显更高。

面试的时候如果先提暴力解法，可以当作“最笨的baseline”一笔带过，重点说“但我们可以利用BST中序遍历有序这个特性，把复杂度降到O(n)甚至更低”。这样反而显得你有全局视野。

从工程意义上讲，暴力解法也反映了一个常见的思维误区：拿到数据先排序，而不是先观察数据本身的规律。真实开发中数据往往自带某些结构特征，善用这些特征往往能省掉一大半无谓的计算。

2. 递归中序遍历：最简单的写法与边界处理

2.1 核心思路：计数器 + 剪枝

递归中序遍历是最直白的写法。我们维护一个计数器，按照“左 → 根 → 右”的顺序访问节点，每经过一个节点计数器加1（或者让k递减，减到0就是答案），当计数器等于k时记录结果并返回。

我习惯用“k递减”而不是“计数器递增”的写法，这样少一个变量，逻辑也更紧凑。

class Solution { private int result; private int count; public int kthSmallest(TreeNode root, int k) { count = k; inorder(root); return result; } private void inorder(TreeNode node) { if (node == null || count == 0) { return; } inorder(node.left); count--; if (count == 0) { result = node.val; return; } inorder(node.right); } }

代码里有两个关键点值得细说。

第一个是剪枝条件count == 0。中序遍历一旦找到第k个节点，理论上整个遍历就可以停止了。如果不加这个条件，递归会继续扫描整棵树，虽然结果不会错，但白白浪费了时间。对于一棵很大的树，能找到答案后立即返回是很重要的优化。

第二个是count和result用成员变量而不是方法返回值。这是递归写法的常见技巧：中序遍历的递归过程很难用返回值传递“第k个节点的值”，因为递归栈的每一层都要做不同的判断，返回值会变得很别扭。用成员变量保存中间状态，代码会清爽很多。

2.2 边界条件与空值处理

LeetCode原题保证了k一定在[1, n]范围内，n是节点总数，所以理论上不会出现找不到答案的情况。但实际写代码还是要注意两个边界：

一是root == null的情况。虽然题目保证k有效，但如果你把这段代码拿到其他地方复用，或者被面试官追问，空树是必须考虑的。上面的写法里inorder(null)会直接因node == null返回，不会报空指针，这是安全的。

二是k刚好等于n的情况，也就是找第n小，即最大值。递归会一路走到最右下角的节点，此时count递减到0，记录右子树最深层节点的值。这个场景下优化不了多少，因为必须遍历到最后一个节点才知道答案。

还有一个小细节：递归过程中如果count == 0提前返回，代码会跳过后续的inorder(node.right)，所以不会出现“找到了答案还被覆盖”的问题。我之前见过有人为了剪枝在if (count == 0) return;后面忘了加return，导致右子树继续被遍历，成员变量result被后面的节点覆盖，结果完全不对。这种坑很隐蔽，测试用例规模一大就翻车。

2.3 复杂度分析与面试变体

递归中序遍历的时间复杂度是O(n)，最坏情况下k等于n，必须走完整个树。空间复杂度是O(h)，h是树高，因为递归栈的深度等于递归层数。

但如果k比较小，实际遍历到第k个节点就停止了，访问的节点数大约是O(h + k)，因为要先沿左子树下沉h层，然后逐步回溯再访问k个节点。这也是为什么我说“中序遍历 + 提前终止”在平均情况下比无脑全遍历要好。

面试官问完这个写法，大概率会追问：“如果我要找第k大的元素呢？”

两种改法。第一种最简单：找第k大 = 找第n-k+1小，先求一次节点总数，再复用中序遍历。第二种更优雅：把中序遍历的顺序反过来，改成“右 → 根 → 左”，计数器逻辑完全不变，第一次访问到的就是最大节点，第k次访问到的就是第k大。

反向中序的代码只需改一行：

// 先遍历右子树，再访问根，最后遍历左子树 inorder(node.right); count--; if (count == 0) { result = node.val; return; } inorder(node.left);

这个变体也延伸出另一道经典题——LeetCode 538“把二叉搜索树转换为累加树”，就是用反向中序遍历累加节点值。所以别小看一个遍历顺序的调整，很多题目都是从这里长出来的。

3. 迭代中序遍历：显式栈写法与工程化考量

3.1 为什么需要迭代写法

递归写法代码最短，但不是没有短板。最直接的问题是递归深度受限于JVM的栈大小，默认情况下栈深度一般在几千到一万层左右。如果一棵BST退化成链表——比如按升序插入节点——树高就等于n，递归到这里直接就StackOverflowError了。

这种极端场景在面试中出现的频率不低，面试官很爱问：“如果这棵树特别深，递归会出什么问题？”

正确的答案是：用迭代 + 显式栈。显式栈分配在堆内存上，可以动态增长，不受调用栈深度限制。这也更贴近真实工程里的做法，因为生产环境中的树结构往往不可控，你无法保证它一定平衡。

迭代写法也为你后面解决“二叉搜索树迭代器”这类题目打基础。LeetCode 173就是一道经典的迭代器题目，要求实现next()和hasNext()，核心逻辑和这道题的迭代中序遍历几乎一样。

3.2 迭代中序的完整实现

迭代中序遍历的思路可以这样理解：手动模拟递归的过程。递归隐含了一个系统栈，我们把它换成显式的Deque。

class Solution { public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 一直往左走，把所有左子节点压栈 while (cur != null) { stack.push(cur); cur = cur.left; } // 弹出栈顶，访问当前节点 cur = stack.pop(); k--; if (k == 0) { return cur.val; } // 转向右子树 cur = cur.right; } return -1; // 不会走到这里，题目保证k有效 } }

拆解一下这个过程。开始时从根节点一路往左，把沿途所有节点压栈。压栈结束后栈顶就是整棵树最左边的节点，也就是最小值。弹出这个节点，k减1，如果k等于0就返回这个节点的值。否则把指针移到它的右子树，重复上述过程。

这里有个容易迷惑的点：为什么弹出节点后要把cur指向cur.right而不是让循环继续弹栈？因为中序遍历的顺序是“左 → 根 → 右”，当前节点作为“根”访问完之后，接下来的访问目标是它的右子树；右子树处理完，才轮到栈里存的那些更上层的节点。这个“先压左链、弹栈转向右”的模式是中序遍历迭代写法的灵魂，建议画图走一遍。

用Java写的时候注意：用ArrayDeque而不是Stack类。Stack继承自Vector，所有方法都加了同步锁，性能差，而且官方文档早就建议用Deque替代了。虽然LeetCode上差别不大，但面试时用ArrayDeque会显得你对Java集合框架更熟悉。

迭代写法的复杂度同样是O(n)时间、O(h)空间，但空间是自己在堆上分配的，不受JVM调用栈限制。这是它与递归最大的工程性差异。

3.3 递归 vs 迭代：不同场景怎么选

从我刷题和实际面试的经验看，这两种写法没有绝对的优劣，关键看场景。

笔试或者限时写代码，优先递归。代码短，出错概率低，调试方便。LeetCode上提交递归写法，性能和迭代差别很小。面试的时候，可以先给递归写法，然后主动补充：“如果树很深，递归可能栈溢出，我可以改成迭代版本。”

如果面试官要求你实现一个迭代器类，比如BSTIterator，那递归就没有用武之地了，必须用显式栈。因为迭代器的核心是“每次调用next()只返回一个值”，你不可能为每次next()都重新递归遍历整棵树。

再来一个实用经验：如果对树的高度没有把握，或者树是通过外部数据动态构建的，工程上优先迭代。我实际做过一个功能，需要从数据库读几千条记录构建树结构，当时直接用递归写，上线后偶尔出现栈溢出，改成迭代就稳了。递归适合“树是已知的、可控制的”场景，迭代适合“树是不可控的”场景。

4. 分治计数法：用左子树大小快速定位第k小

4.1 利用BST定义缩小搜索范围

中序遍历解法的时间复杂度是O(n)，但题目其实给了一个更精妙的思路：利用BST的定义，不需要遍历所有节点也能定位第k小的元素。

BST里，根节点的左子树包含所有比根小的节点。假设左子树的节点数为leftSize，那么：

• 如果leftSize >= k，说明第k小的元素一定在左子树里，直接去左子树找第k小
• 如果leftSize + 1 == k，说明第k小的元素就是根节点本身
• 如果leftSize + 1 < k，说明第k小的元素在右子树里，去右子树找第k - leftSize - 1小

这个思路像不像二分查找？每次根据左子树的大小，把搜索范围缩小到左子树、根节点或右子树，一次排除一大半的节点。这是这道题从“O(n)遍历”升级到“O(h)定位”的关键所在。

4.2 基础版实现：动态计算子树节点数

最简单的实现方式是每次计算左子树的节点数，然后递归往下走。

class Solution { public int kthSmallest(TreeNode root, int k) { int leftSize = countNodes(root.left); if (leftSize >= k) { return kthSmallest(root.left, k); } else if (leftSize + 1 < k) { return kthSmallest(root.right, k - leftSize - 1); } else { return root.val; } } private int countNodes(TreeNode node) { if (node == null) { return 0; } return 1 + countNodes(node.left) + countNodes(node.right); } }

这种写法的优点是代码逻辑清晰，完全基于BST定义，不需要遍历框架。缺点是每次判断都要计算左子树的节点数，而countNodes本身是O(n)的。对于一个倾斜严重的树，走到第k小的节点之前可能要重复计算很多次，最坏时间复杂度退化成O(n^2)。

所以在LeetCode上，这个解法通常不是最优解，但它是一种很重要的思维训练：用“排除法”而不是“遍历法”来解决问题。很多树结构上的问题都可以用这种分治思想来做。

4.3 进阶优化：维护size字段实现O(h)查询

题目最后有一个进阶要求：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第k小的值，你将如何优化？

这就是关键。动态计算子树大小在大规模查询场景下不可行，因为每次查询都可能是O(n^2)。正确做法是：每个节点维护一个size字段，表示以该节点为根的子树包含多少个节点。插入和删除的时候同步更新受影响节点的size，查询的时候直接用size值判断方向。

这个思路对应到Java实现，有两种落地方式。

第一种是给TreeNode加字段。LeetCode的TreeNode类不能改，但你可以自己定义一个带size的节点类：

class TreeNodeWithSize { int val; TreeNodeWithSize left; TreeNodeWithSize right; int size; // 以当前节点为根的子树节点数 TreeNodeWithSize(int val) { this.val = val; this.size = 1; } }

插入时，沿着路径每经过一个节点就让它的size加1；删除时，把节点摘掉后沿着路径让每个节点的size减1。查询第k小时，直接读左子树的size，O(h)时间就能返回。

第二种是用现成的数据结构。Java的TreeMap底层是红黑树，支持按key查找，但TreeMap不直接暴露“第k小的key”这个操作。真要实现，得自己扩展或者用第三方库。实际工程里如果数据量不大，可以把树节点值维护在一个有序结构里，牺牲一点插入删除性能换取查询的O(log n)。比如用ArrayList保持有序，插入用二分查找定位，查询直接取下标。这种方式简单粗暴，数据量小的时候反而更实用。

说到底，这道题的进阶解法在面试里主要考察的是你有没有“预处理”的意识。BST的size字段就类似于数据库里的索引，预先把信息算好存起来，查询时不现算，这就是典型的空间换时间。

4.4 三种方案横向对比

到这里，这道题的三种主流解法都齐了，我整理了一张对比表，方便你直接记忆。

注意区分：递归和迭代中序遍历的时间复杂度都是O(n)，但k较小时实际运行会提前终止，访问节点数大约是O(h + k)。分治计数法如果每次都动态计算size，最坏情况下反而更慢；只有配合预处理的size字段，才能稳定达到O(h)。

面试时我一般这样展示层次：先给递归中序（最简单正确），再主动补充迭代版本（展示工程意识），最后提分治 + size字段（展示对进阶优化的理解）。这一套组合拳下来，面试官基本没有继续追问的空间了。

5. 面试追问与扩展：从这道题延伸出的高频考点

5.1 面试官最爱追问的几个问题

这道题几乎必然引出追问，我整理了几个高频问题，每个都值得自己动手实现一遍。

第一个：“如果找第k大呢？”答案在上面提过，反向中序遍历，或者转换成找第n-k+1小。面试时建议两种都说一遍，然后提到LeetCode 538累加树就是反向中序的应用。

第二个：“如果这不是BST，只是一个普通二叉树呢？”那中序遍历有序的性质就不成立了。只能把节点值全部取出来，用快速选择算法（QuickSelect）做到平均O(n)，或者用大小顶堆处理“动态数据流中的第k大”类问题。

第三个：“如果k=1和k=n分别等于什么？”k=1是最小值，k=n是最大值。最小值就是最左节点，最大值就是最右节点。这两个特殊情况都可以不用遍历整棵树，直接沿左或右边界走下去。

第四个：“如果树非常大，内存装不下怎么办？”这就是典型的分布式/外部场景了。单机可以用外部排序，分块读入；分布式可以用近似算法，比如水塘抽样。面试官大概率不会往这个方向深挖，但你提一句“大数据量下要分治处理”能加分。

第五个：“中序遍历为什么有序？”这个问题看似基础，但很多人答不好。一定要答到“BST定义保证了左子树全部小于根、右子树全部大于根，中序先左后根再右，自然形成升序”。

5.2 实战中容易踩的坑

代码层面的坑我前面提了几个，这里再集中整理一遍。

第一个坑是k的计数起点。题目明确说了k从1开始，所以第一个访问的节点对应k=1。有人写习惯了数组下标0开始的逻辑，把判断写成k == 1提前返回，结果第一个节点就返回了，完全不对。

第二个坑是结果覆盖。递归版本里如果剪枝条件不完整，找到结果后继续遍历右子树，result被后面的值覆盖。记住：找到答案后必须立即终止后续遍历。

第三个坑是栈的选择。Java里用Stack类虽然也能跑通，但性能差、不推荐。面试时用ArrayDeque，同时能说出来为什么，这是加分项。

第四个坑是空间复杂度表述含糊。中序遍历的空间复杂度是O(h)而不是O(n)，只有在最坏情况（链状树）下h才等于n。面试时如果说O(n)，面试官可能会追问“确定吗”，这时候要能意识到树高和节点数的区别。

第五个坑是LeetCode环境下的输入处理。题目给的是已经构建好的TreeNode，不需要自己解析。但如果你在自己本地写测试，要会手动构建树，这是基本功，别在细节上翻车。

5.3 从这道题延伸出去的相关题目

这道题做完，强烈建议立刻刷几个相关题目巩固，思路是相通的。

LeetCode 98“验证二叉搜索树”：核心思路就是中序遍历后检查是否严格递增。我当年是拿这道题练熟了中序遍历，再去做230题就轻车熟路了。

LeetCode 173“二叉搜索树迭代器”：要求实现一个迭代器，next()返回下一个最小的值。这就是用显式栈的中序遍历拆成单步操作，做完230题再刷173题，几乎白送。

LeetCode 230的姊妹题还有“剑指Offer 54 二叉搜索树的第k大节点”，思路就是反向中序遍历，代码改一行顺序就好。

另外热词里还出现了“不同的二叉搜索树”、“最优二叉搜索树c语言”这些词条。LeetCode 96“不同的二叉搜索树”和95“不同的二叉搜索树II”考察的是动态规划和卡特兰数，跟这道题不同维度的知识。虽然不算同一类型，但都属于“二叉搜索树”这个专题，建议一起做掉，把BST相关的套路一次性打通。

刷到后面你会发现，BST的题目其实就那么几个套路：中序遍历有序、左小右大递归判断、利用子树大小做分治、构建时用有序序列。230题是把这些套路串起来的最短路径。

这道题我个人刷了不下五遍。每次刷都有新收获：第一次学会了中序遍历，第二次理解了显式栈的写法，第三次才明白分治计数法的精妙，第四次能不看答案把进阶解法讲清楚，第五次纯粹是为了面试前找手感。建议你也别只满足于AC一次，隔两周再做一遍，看看自己能不能写出第二种解法，这种“重复刷题”的收益比做十道新题都大。