二叉搜索树中第K小的元素——Morris遍历与进阶Follow-up
二叉搜索树中第K小的元素——Morris遍历与进阶Follow-up
适读人群：Java 后端工程师、准备大厂面试的同学 | 阅读时长：约20分钟 | 难度：Medium
开篇故事
230 题本身不难，基础做法是中序遍历取第 k 个，几行代码搞定。但这道题在大厂面试里经常作为 follow-up 题出现，而且追问会很刁钻。
我被问到过这样的 follow-up：如果这棵 BST 经常被修改（插入/删除），而且经常被查询第 k 小的值，你会怎么优化？
这个问题的标准答案是：给每个节点附加一个 leftCount 属性，记录左子树的节点数。这样查询第 k 小的操作从 O(h) 的二分搜索完成（类似顺序统计树），而插入/删除时只需要更新路径上节点的计数，O(h) 时间维护。
后来我还被问到过：只要求 O(1) 空间的解法怎么做？答案就是 Morris 中序遍历，上一篇刚讲过。
这篇文章把三种解法都给出来，最后专门讲 follow-up 的优化方案，这部分在面试中能展示你对工程权衡的思考能力。
一、题目解析
题目：LeetCode 230. 二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
示例：
输入：root = [3,1,4,null,2], k = 1
输出：1
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3进阶：如果二叉搜索树经常被修改（插入/删除操作），并且你需要频繁地查找第 k 小的值，你将如何优化算法？
二、解法一：中序遍历收集序列
思路
中序遍历 BST 得到有序序列，然后直接返回第 k-1 个元素（0-indexed）。
class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> inorder = new ArrayList<>();
collectInorder(root, inorder);
return inorder.get(k - 1);
}
private void collectInorder(TreeNode node, List<Integer> list) {
if (node == null) return;
collectInorder(node.left, list);
list.add(node.val);
collectInorder(node.right, list);
}
}复杂度分析
- 时间复杂度：O(n)。遍历整棵树。
- 空间复杂度：O(n)。存储序列。
三、解法二：中序遍历提前退出
思路
不需要存储完整序列，用递归或迭代的中序遍历，数到第 k 个节点就立刻返回，不再继续遍历。
完整代码（递归版）
class Solution {
private int count = 0;
private int result = 0;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return result;
}
private void inorder(TreeNode node, int k) {
if (node == null) return;
inorder(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
inorder(node.right, k);
}
}完整代码（迭代版，更优雅）
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
k--;
if (k == 0) return curr.val; // 找到第 k 小的元素
curr = curr.right;
}
return -1; // 题目保证 k 有效，不会到达这里
}
}复杂度分析
- 时间复杂度：O(h + k)。h 是树的高度（到达最小节点需要 h 步），然后还需要中序遍历 k 个节点。
- 空间复杂度：O(h)。栈深度等于树的高度。
四、解法三：最优解法——Morris 中序遍历
思路
用 Morris 中序遍历实现 O(1) 空间，在遍历过程中计数，找到第 k 个节点立刻返回。
class Solution {
public int kthSmallest(TreeNode root, int k) {
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
// 没有左子树，访问当前节点
k--;
if (k == 0) return cur.val;
cur = cur.right;
} else {
// 找左子树的最右节点（中序前驱）
TreeNode predecessor = cur.left;
while (predecessor.right != null && predecessor.right != cur) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 第一次到达：建立线索，移动到左子树
predecessor.right = cur;
cur = cur.left;
} else {
// 第二次到达：恢复线索，访问当前节点
predecessor.right = null;
k--;
if (k == 0) return cur.val;
cur = cur.right;
}
}
}
return -1;
}
}复杂度分析
- 时间复杂度：O(h + k)。最坏 O(n)。
- 空间复杂度：O(1)。不使用额外空间，只有常数个指针。
提交结果：时间击败约 95% 用户，空间击败约 99% 用户（O(1) 空间碾压）。
五、进阶 Follow-up：频繁修改+频繁查询的优化
问题分析
当前解法每次查询需要 O(h + k) 时间，如果查询频繁，这个开销会很大（最坏 O(n)）。
解决方案：节点附加左子树计数
给每个节点增加一个属性 leftCount，记录以该节点为根的子树中，在该节点左侧的节点总数（即小于该节点值的节点数）。
有了 leftCount，查询第 k 小就变成了：
- 如果
node.leftCount + 1 == k，当前节点就是答案 - 如果
k <= node.leftCount，答案在左子树，递归处理node.left（k 不变） - 如果
k > node.leftCount + 1，答案在右子树，递归处理node.right（k 更新为k - node.leftCount - 1）
// 增强节点结构
class AugmentedTreeNode {
int val;
int leftCount; // 左子树节点数
AugmentedTreeNode left, right;
AugmentedTreeNode(int val) { this.val = val; }
}
class OptimizedSolution {
// 查询第 k 小，时间 O(h)
public int kthSmallest(AugmentedTreeNode root, int k) {
AugmentedTreeNode node = root;
while (node != null) {
if (node.leftCount + 1 == k) return node.val;
else if (k <= node.leftCount) node = node.left;
else {
k -= node.leftCount + 1;
node = node.right;
}
}
return -1;
}
// 插入节点，维护 leftCount，时间 O(h)
public AugmentedTreeNode insert(AugmentedTreeNode root, int val) {
if (root == null) return new AugmentedTreeNode(val);
if (val < root.val) {
root.leftCount++; // 新节点在左子树，leftCount 增加
root.left = insert(root.left, val);
} else {
root.right = insert(root.right, val);
}
return root;
}
}性能对比
| 方案 | 查询时间 | 插入时间 | 空间 |
|---|---|---|---|
| 基础中序遍历 | O(h + k) | O(h) | O(h) |
| Morris 遍历 | O(h + k) | O(h) | O(1) |
| leftCount 增强 | O(h) | O(h) | O(n) 额外 |
leftCount 增强方案在频繁查询场景下，查询时间从 O(h + k) 降到 O(h)（对平衡 BST 是 O(logn)），代价是每个节点多存一个整数。
六、举一反三
同类题目
LeetCode 703. 数据流中的第K大元素 维护大小为 K 的最小堆，堆顶就是第 K 大元素。
LeetCode 215. 数组中的第K个最大元素 快速选择算法 O(n) 时间，或堆排序 O(n logk)。
LeetCode 378. 有序矩阵中第K小的元素 二分 + 计数，O(n log(max-min)) 时间。
七、踩坑实录
坑一：k 用完局部变量还是实例变量
递归版本里，每次发现当前节点是第 k 小时，需要停止继续递归。用实例变量（count 和 result）的写法里，count == k 之后函数还会继续返回，但不会再修改 result。用 bool 标记或返回值来中止递归是更清洁的写法，但代码略复杂。迭代版本不存在这个问题——直接 return 即可。
坑二：Morris 遍历提前返回后树结构未恢复
如果在 k 减到 0 时立刻 return，此时树中可能还有未恢复的线索（前驱节点的 right 指向了某个祖先节点）。对于 LeetCode 这类题目影响不大，但在生产代码里需要完整恢复树结构。如果有这个顾虑，可以在找到第 k 小后继续遍历完以恢复树结构。
坑三：leftCount 增强方案的删除操作更复杂
插入时维护 leftCount 较简单（只影响路径上的节点）。但删除时，删除一个节点后，其所有祖先中包含该节点在左子树的那些节点的 leftCount 都需要减 1，这需要在删除时记录被删节点的路径。这部分代码相对复杂，面试里一般只需要讲清楚思路和维护方式，不需要完整实现。
坑四：第 k 小和第 k 大的转换
题目是第 k 小。如果要求第 k 大，可以用"反向中序遍历"（先右后左），或者转换为"第 n-k+1 小"（n 是总节点数）。
坑五：k 从 1 开始还是 0 开始
题目说从 1 开始计数，代码里记得用 k-- 后检查 k == 0，或者在访问时先减，后判断。
八、总结
230 题是 BST 中序有序性的直接应用。基础做法几行代码，重点在 follow-up——如何设计一个支持高频修改和高频查询的高效数据结构。
leftCount 增强方案是"顺序统计树"的简化版，在工程上是解决这类问题的标准思路。面试里如果能主动提出这个方向，展示出你对数据结构设计权衡的思考（牺牲部分空间换取更好的查询性能），是非常强的加分项。