LeetCode 230. 二叉搜索树中第 K 小的元素
题目描述
题意分析
给定一棵二叉搜索树和整数
k，返回树中按数值从小到大排列后，第k个节点的值。排名从1开始，返回的是节点值，不是节点所在的层数或遍历下标。题目保证树非空且
1 <= k <= n，所以答案一定存在。树不一定平衡，也没有要求修改树；解题时可以利用二叉搜索树的有序性质，避免把所有节点重新排序。
解法：迭代中序遍历
核心思路
[!blue]
二叉搜索树中，左子树的值小于当前节点，右子树的值大于当前节点。因此按“左子树、当前节点、右子树”的中序顺序访问，得到的就是升序序列，第
k次访问的节点便是答案。用显式栈模拟递归。沿左孩子不断入栈，是把当前节点暂存起来，等待较小的左子树处理完成；走到空节点后，栈顶就是下一个应当访问的节点。入栈只是等待，弹栈才是一次正式的中序访问，所以应在弹栈时将
k减一，减到零就返回该节点的值。当前节点访问后，把
root转向它的右孩子，再沿这棵右子树的左链入栈，寻找下一批更大的值。如果没有右孩子，下一轮直接弹出栈中等待的祖先。这样既不会漏掉右子树，也不会重复访问已经处理的节点。题目保证排名有效，因此循环一定会在第
k次弹栈时返回，不会在答案出现之前耗尽所有候选。找到目标后立即停止，无需保存完整的有序序列。进阶：频繁增删和查询。 可以在每个节点维护子树节点数
size = 1 + size(left) + size(right)，空树大小为0。查询时令leftSize为左子树节点数：若k <= leftSize就进入左子树；若k == leftSize + 1就返回当前值；否则进入右子树，并令k -= leftSize + 1，跳过左子树和当前节点。初次建立这些计数需要一次后序遍历。插入或删除后，必须沿受影响的路径自下而上重算
size；如果用平衡树，旋转后也要先更新较低节点、再更新新的子树根。维护正确时，每次排名查询只沿一条路径，耗时为 $O(h)$；只有同时保证树平衡，增删与查询才能稳定在 $O(\log n)$。下方代码对应单次查询，不依赖额外的计数信息。
解题步骤
- 创建空栈，从根节点开始，沿左孩子逐个入栈，直到遇到空节点。
- 弹出栈顶，作为下一个中序访问的节点；将
k减一，为零时立即返回节点值。- 将当前指针转向该节点的右孩子，继续执行左链入栈和弹栈访问。
- 重复上述过程，直到找到题目保证存在的第
k个节点。
代码实现
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为树高。返回前已经弹出k个节点，尚留在栈中的节点最多h个，因此总入栈次数也不超过这个量级；最坏为 $O(n)$。- 空间复杂度：$O(h)$，栈保存沿树路径等待访问的节点。平衡树为 $O(\log n)$，退化成链时为 $O(n)$。
关键点总结
[!green]
- 中序访问顺序就是升序排名，不需要重新排序。
- 入栈负责保留返回位置，弹栈负责正式访问，排名只在弹栈时递减。
- 子树计数可以让多次查询跳过整棵子树，但前提是每次结构修改后都正确维护计数。
易错点总结
[!yellow]
- 入栈时就减少
k，会按探索路径而非中序顺序计数，得到错误排名。- 弹栈后忘记转向该节点的右孩子，会漏掉整个右子树。
- 反向中序“右、根、左”得到的是从大到小的顺序，与本题第
k小相反。- 二叉搜索树不保证平衡，不能把遍历栈空间或进阶查询时间无条件写成对数级。
- 进阶中进入右子树时，必须同时减去左子树大小和当前节点的一位排名。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 173. 二叉搜索树迭代器 | 中等 | BST中序迭代器按升序逐个返回节点，读取到第k项即可得到答案。 |
| 补充题 213. 二叉搜索树中第 k 小的节点 | 中等 | 都按中序遍历取得第 k 个节点；补充题还规定越界时返回 -1。 |
| 98. 验证二叉搜索树 | 中等 | 通过中序访问利用二叉搜索树的升序性质；本题在第 k 次访问时取值，该题验证整个序列严格递增。 |
| 99. 恢复二叉搜索树 | 中等 | 通过中序访问利用二叉搜索树的升序性质；本题在第 k 次访问时取值，该题根据下降位置定位交换节点。 |
| 530. 二叉搜索树的最小绝对差 | 简单 | 通过中序访问利用二叉搜索树的升序性质；本题在第 k 次访问时取值，该题比较相邻中序值的差。 |