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。如果k3第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-k1小先求一次节点总数再复用中序遍历。第二种更优雅把中序遍历的顺序反过来改成“右 → 根 → 左”计数器逻辑完全不变第一次访问到的就是最大节点第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) { DequeTreeNode 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小时直接读左子树的sizeO(h)时间就能返回。第二种是用现成的数据结构。Java的TreeMap底层是红黑树支持按key查找但TreeMap不直接暴露“第k小的key”这个操作。真要实现得自己扩展或者用第三方库。实际工程里如果数据量不大可以把树节点值维护在一个有序结构里牺牲一点插入删除性能换取查询的O(log n)。比如用ArrayList保持有序插入用二分查找定位查询直接取下标。这种方式简单粗暴数据量小的时候反而更实用。说到底这道题的进阶解法在面试里主要考察的是你有没有“预处理”的意识。BST的size字段就类似于数据库里的索引预先把信息算好存起来查询时不现算这就是典型的空间换时间。4.4 三种方案横向对比到这里这道题的三种主流解法都齐了我整理了一张对比表方便你直接记忆。解法时间复杂度空间复杂度核心优势适用场景递归中序遍历O(n)O(h)代码最短、最不容易出错笔试快速AC、k较小时迭代中序遍历O(n)O(h)不会栈溢出、流程可控树很深、工程代码分治计数法最坏O(n^2)O(h)思路精巧、排除式搜索配合size字段做频繁查询注意区分递归和迭代中序遍历的时间复杂度都是O(n)但k较小时实际运行会提前终止访问节点数大约是O(h k)。分治计数法如果每次都动态计算size最坏情况下反而更慢只有配合预处理的size字段才能稳定达到O(h)。面试时我一般这样展示层次先给递归中序最简单正确再主动补充迭代版本展示工程意识最后提分治 size字段展示对进阶优化的理解。这一套组合拳下来面试官基本没有继续追问的空间了。5. 面试追问与扩展从这道题延伸出的高频考点5.1 面试官最爱追问的几个问题这道题几乎必然引出追问我整理了几个高频问题每个都值得自己动手实现一遍。第一个“如果找第k大呢”答案在上面提过反向中序遍历或者转换成找第n-k1小。面试时建议两种都说一遍然后提到LeetCode 538累加树就是反向中序的应用。第二个“如果这不是BST只是一个普通二叉树呢”那中序遍历有序的性质就不成立了。只能把节点值全部取出来用快速选择算法QuickSelect做到平均O(n)或者用大小顶堆处理“动态数据流中的第k大”类问题。第三个“如果k1和kn分别等于什么”k1是最小值kn是最大值。最小值就是最左节点最大值就是最右节点。这两个特殊情况都可以不用遍历整棵树直接沿左或右边界走下去。第四个“如果树非常大内存装不下怎么办”这就是典型的分布式/外部场景了。单机可以用外部排序分块读入分布式可以用近似算法比如水塘抽样。面试官大概率不会往这个方向深挖但你提一句“大数据量下要分治处理”能加分。第五个“中序遍历为什么有序”这个问题看似基础但很多人答不好。一定要答到“BST定义保证了左子树全部小于根、右子树全部大于根中序先左后根再右自然形成升序”。5.2 实战中容易踩的坑代码层面的坑我前面提了几个这里再集中整理一遍。第一个坑是k的计数起点。题目明确说了k从1开始所以第一个访问的节点对应k1。有人写习惯了数组下标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一次隔两周再做一遍看看自己能不能写出第二种解法这种“重复刷题”的收益比做十道新题都大。
