230. 二叉搜索树中第K小的元素#
生活中的算法#
想象你在图书馆的书架前，所有书籍都按照编号从小到大排列。现在要找到第5本编号最小的书，你会怎么做？很简单，只需要从左往右数到第5本即可。
这正是二叉搜索树（BST）的天然特性——中序遍历的结果就是有序序列。今天我们要解的这道题，就像在BST这座”数字图书馆”中，快速找到第K本”书”。
问题描述#
题目目标#
给定一棵二叉搜索树 root 和一个整数 k，请返回这棵树中第 k 小的节点值。
示例 1#
输入： root = [3,1,4,null,2], k = 1
输出： 1
二叉搜索树示意：
3
/ \
1 4
\
2说明： 二叉搜索树的中序遍历结果是升序序列 [1,2,3,4]，其中第 1 小的元素是 1。
补充说明#
- 二叉搜索树满足“左子树所有节点值 < 根节点值 < 右子树所有节点值”。
- 因此中序遍历天然能按从小到大的顺序访问节点。
最直观的解法：中序遍历法#
就像在图书馆里把书全部搬到地上再数到第k本，我们可以通过中序遍历将BST转换为有序数组，然后直接取第k-1个元素。
算法步骤#
- 对BST进行中序遍历，得到升序数组
- 返回数组中第k-1个元素
用示例树模拟这个过程：
中序遍历顺序：1→2→3→4
当k=3时，数组第三个元素是3Java实现：
class Solution {
public int kthSmallest(TreeNode root, int k) {
// 用于保存中序遍历结果（BST 中序结果天然有序）
List<Integer> list = new ArrayList<>();
// 执行中序遍历，把所有节点按升序加入 list
inorder(root, list);
// 第 k 小元素在 0-based 下标里对应 k-1
return list.get(k-1);
}
private void inorder(TreeNode node, List<Integer> list) {
// 递归终止条件：空节点直接返回
if (node == null) return;
// 先遍历左子树（更小的值）
inorder(node.left, list);
// 再访问当前节点
list.add(node.val);
// 最后遍历右子树（更大的值）
inorder(node.right, list);
}
}优化解法：遍历时提前返回#
但如果我们只需要第k本，何必要把整个书架都搬空？发现数到第k本时可以直接停止！
改进思路#
- 在中序遍历过程中记录访问次序
- 当计数器等于k时立即返回结果
- 利用BST特性提前终止遍历
算法步骤（迭代法）#
- 使用栈模拟中序遍历
- 每次弹出节点时计数器加1
- 当计数器等于k时立即返回当前节点值
用示例树模拟（k=3）：
栈操作流程：
1. 3入栈→3的左孩子1入栈→1的左孩子null
2. 弹出1，计数器=1≠3
3. 处理1的右子树2→2入栈→2的左孩子null
4. 弹出2，计数器=2≠3
5. 弹出3，计数器=3→找到答案3！Java代码：
class Solution {
public int kthSmallest(TreeNode root, int k) {
// 栈用于模拟递归版中序遍历
Deque<TreeNode> stack = new ArrayDeque<>();
// 当前访问指针
TreeNode cur = root;
// 记录已经访问了多少个节点
int count = 0;
// 只要还有节点可深入或栈中仍有待处理节点，就继续遍历
while (cur != null || !stack.isEmpty()) {
// 一路向左，把路径节点压栈
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 弹出当前最小的未处理节点
cur = stack.pop();
// 访问计数 +1；若刚好是第 k 个，直接返回答案
if (++count == k) return cur.val;
// 转向该节点右子树，继续中序流程
cur = cur.right;
}
// 题目保证 k 合法，这里仅作兜底返回
return -1; // 不会执行到这里
}
}终极优化：Morris遍历法#
如果连栈都不想用怎么办？就像在书架间穿梭时，用临时标记记录回程路线！
Morris遍历原理#
- 利用叶子节点的空指针记录回溯路径
- 在遍历时临时修改树结构，之后恢复
- 实现O(1)空间复杂度
算法步骤#
- 当前节点cur初始化为根节点
- 当cur不为空时循环：
- 如果cur无左子树：
- 计数器加1，若等于k则返回
- cur移向右子树
- 否则：
- 找到cur左子树的最右节点pre
- 若pre的右指针为空：将其指向cur，cur移向左子树
- 若pre的右指针为cur：恢复为空，处理当前节点，cur移向右子树
- 如果cur无左子树：
示例运行（k=3）：
初始状态：
3
/ \
1 4
\
2
步骤：
1. cur=3，左子树存在
2. pre=2（1的右子树的最右）
3. pre.right=3，cur=1
4. cur=1，左子树不存在→计数器=1≠3→cur=1.right=2
5. cur=2，左子树不存在→计数器=2≠3→cur=2.right=3
6. 此时pre=2的右指针指向3→恢复pre.right=null→计数器+1=3→返回3Java实现：
class Solution {
public int kthSmallest(TreeNode root, int k) {
// 记录已访问节点个数
int count = 0;
// 当前遍历节点指针
TreeNode cur = root;
// Morris 中序遍历主循环
while (cur != null) {
// 情况1：没有左子树，当前节点可直接访问
if (cur.left == null) {
// 访问当前节点；若是第 k 个则返回
if (++count == k) return cur.val;
// 转向右子树继续
cur = cur.right;
} else {
// 情况2：有左子树，先找左子树最右节点（中序前驱）
TreeNode pre = cur.left;
// 一直向右走，直到最右，或遇到已建立的线索指针
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
// 若前驱右指针为空：建立“线索”回到 cur，然后先去左子树
if (pre.right == null) { // 建立线索
pre.right = cur;
cur = cur.left;
} else { // 拆除线索
// 若前驱右指针已指向 cur：说明左子树处理完，先恢复树结构
pre.right = null;
// 再访问当前节点；若是第 k 个则返回
if (++count == k) return cur.val;
// 最后转向右子树
cur = cur.right;
}
}
}
// 题目保证 k 合法，这里仅作兜底返回
return -1;
}
}解法对比#
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 递归中序遍历 | O(n) | O(n) | 简单但空间消耗大 |
| 迭代中序遍历 | O(n) | O(h) | 最优平衡（h为树高） |
| Morris遍历 | O(n) | O(1) | 空间最优但修改树结构 |
题目模式总结#
这道题揭示了BST类问题的核心解法：
- 中序遍历有序性：BST问题的解题基石
- 遍历优化：通过提前终止或空间优化提升效率
- Morris技巧：在有限制条件下的空间优化方案
同类问题扩展：
- 验证二叉搜索树
- BST转换为累加树
- BST中的众数
解决这类问题的通用思路：
- 确认是否利用中序特性
- 根据空间限制选择遍历方式
- 在遍历过程中记录关键信息
小结#
通过这道题，我们不仅掌握了三种不同时空复杂度的解法，更重要的是理解了BST的核心特性——中序遍历的有序性。就像在有序的书架上找书，关键是要掌握高效的检索方法。
记住：算法优化往往是在时空复杂度之间寻找平衡。在面试中，通常优先推荐迭代法中序遍历法，既保证了O(h)的空间复杂度，又易于理解和实现。