LeetCode 230. 二叉搜索树中第 K 小的元素
目录
题目描述
题意分析
给一棵二叉搜索树的根节点和正整数
k，返回树中所有节点值里第k小的那个。二叉搜索树的定义是：对任意节点，左子树中所有值都严格小于它，右子树中所有值都严格大于它，因此节点值互不重复，「第k小」没有并列的歧义。约束给了两个信号。第一，题目保证
1 ≤ k ≤ 节点总数，也就是答案必然存在，不需要处理越界返回什么；第二，节点数量上限是一万，说明即使把整棵树完整走一遍也来得及，但进阶部分特意问「如果要频繁查询、并且树会被反复插入删除该怎么优化」，这提示朴素做法的代价集中在「每次查询都要重新扫描」，可以靠在节点上额外维护子树规模来摊掉。边界主要是三类：
k = 1时答案是整棵树最靠左的那个节点；k等于节点总数时答案是最靠右的节点；输入可能退化成一条只有左孩子或只有右孩子的链，此时树高等于节点数，任何依赖树高的空间估计都要按最坏情况给。
解法：迭代中序遍历
核心思路
问题关键：BST 满足「左子树 < 根 < 右子树」，因此中序遍历得到严格递增序列。第
k小，就是中序遍历中第k个被访问的节点。为什么选迭代中序：收集全部节点再排序没有利用 BST 的有序性；收集中序数组又会多占 $O(n)$ 空间。显式栈可以按需生成升序节点，弹出第
k个时立即返回，而且所有状态都在函数内部，比递归加成员变量更容易控制提前结束。不变量：每轮弹栈前，栈保存着通往「下一个尚未访问的最小节点」的路径；已经弹出的节点严格递增。弹出一个节点就令
k--，所以k始终表示距离目标还差多少次访问。正确性：一路压入左孩子后，栈顶没有未处理的更小节点，因此它是当前最小的未访问节点。弹出它，再对其右子树重复相同过程，就按升序逐个访问所有节点。于是
k第一次减为0时，当前值恰好是第k小。题目保证k合法，所以一定能在循环中返回。
解题步骤
- 从根开始不断压入左孩子，直到为空。
- 弹出栈顶，这一步等价于中序遍历的「访问根」；令
k--，若为0立即返回节点值。- 转向该节点的右孩子，继续把其左链压栈；重复以上过程。
口述样例：
[5,3,6,2,4,null,null,1]的弹栈顺序从1,2,3开始，k = 3时弹到3便返回，后面的4,5,6无需访问。边界检查：
k = 1返回最左节点；树退化成单链时逻辑不变，只是栈深可能达到节点数。
代码实现
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
while (true) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (--k == 0) {
return root.val;
}
root = root.right;
}
}
}
func kthSmallest(root *TreeNode, k int) int {
stack := []*TreeNode{}
for {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
k--
if k == 0 {
return root.Val
}
root = root.Right
}
}
复杂度分析
- 时间复杂度：$O(h+k)$，
h为树高。开始最多沿左链走h层，此后每个节点至多入栈、出栈一次，访问到第k个节点就停止；最坏仍为 $O(n)$。- 空间复杂度：$O(h)$，显式栈最多保存一条根到叶子的路径；平衡树为 $O(\log n)$，退化树为 $O(n)$。
关键点总结
- BST 的中序遍历天然有序，不需要重新排序。
- 弹栈才代表真正访问节点，
k--必须放在这里。- 只查询一次时按需遍历最直接；若频繁查询且树会更新，可在节点中维护子树大小，把单次查询降为 $O(h)$，代价是插入、删除时同步维护计数。
易错点总结
- 把遍历顺序写成「根、左、右」，
k = 1会返回根而不是最小值。- 压完左链后忘记转向弹出节点的右子树，会漏掉位于右子树中的排名。
- 把空间复杂度固定写成 $O(\log n)$；BST 不保证平衡，单链时应为 $O(n)$。
- 求第
k大时仍使用「左、根、右」；应镜像为「右、根、左」。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 94. 二叉树的中序遍历 | 简单 | 中序遍历的裸模板，要求输出完整序列，没有提前终止的空间 |
| 98. 验证二叉搜索树 | 中等 | 反向利用同一性质，检查中序序列是否严格递增 |
| 173. 二叉搜索树迭代器 | 中等 | 把遍历拆成可暂停的迭代器，需要显式栈保存现场，均摊 $O(1)$ |
| 285. 二叉搜索树中的中序后继 | 中等 | 只求某个节点的下一个访问对象，可沿路径二分而不必遍历 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 同样求第 k 小，但载体是行列有序的矩阵，靠值域二分或多路归并 |
| 426. 将二叉搜索树转化为排序的双向链表 | 中等 | 遍历中改指针，需要记录前驱节点并在结尾首尾相接 |
| 538. 把二叉搜索树转换为累加树 | 中等 | 反向遍历累加后缀和，原地改写节点值 |
| 897. 递增顺序搜索树 | 简单 | 遍历中重建结构，把树拉成只有右孩子的斜链 |
| 1038. 从二叉搜索树到更大和树 | 中等 | 与 538 同型，可用来检验反向遍历模板是否写熟 |
| LCR 052. 递增顺序搜索树 | 简单 | 897 的 LCR 版本，可对照练习递归与迭代两种重建写法 |
| LCR 054. 把二叉搜索树转换为累加树 | 中等 | 538 的 LCR 版本，输入输出一致 |
| 剑指 Offer 36. 二叉搜索树与双向链表 | 中等 | 426 的剑指版本，额外强调不能创建新节点 |
| 剑指 Offer 54. 二叉搜索树的第k大节点 | 简单 | 本题的镜像，需把访问顺序整体反向成「右 → 根 → 左」 |
| 面试题 04.05. 合法二叉搜索树 | 中等 | 98 的同题，注意相等值是否合法的判定细节 |
| 面试题 17.12. BiNode | 简单 | 与 897 目标相同，但要求复用原节点并把左指针置空 |