87.叉搜索树中第K小的元素
题目
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
示例 1：
- 输入：root = [3,1,4,null,2], k = 1
- 输出：1
示例 2：
- 输入：root = [5,3,6,2,4,null,null,1], k = 3
- 输出：3
提示：
- 树中的节点数为 n 。
- 1 <= k <= n <= 104
- 0 <= Node.val <= 104
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
思路
上一题（530 最小绝对差）我们确立了一条铁律：
▎ BST 的中序遍历（左 → 根 → 右）产出的序列必然是升序的。
那"第 k 小"就是中序序列里的第 k 个元素。问题瞬间从"在树里找"变成"在一个升序数组里取第 k 项"。
第 0 步：最直白的做法
中序遍历，把所有值倒进一个数组，返回 values[k - 1]。
return values[k - 1] // k 是从 1 开始的，数组下标从 0 开始
这样一定对，O(n) 时间 O(n) 空间。但它做了两件多余的事：遍历了整棵树，还存下了全部值。
第 1 步：不用存数组，边走边数
既然只要第 k 个，那就用一个计数器 count：每次中序访问到一个节点就 count++，数到 k 就是它。
第 2 步：数到了就立刻停
这是本题相比 530 的关键增量。530 必须看完所有相邻对才能确定最小差，但这题——第 k 个一拿到，后面的节点全都不用看了。
于是复杂度从 O(n) 变成 O(H + k)： - H 是树高，代表"从根一路向左下到最小元素"的路程 - k 是从最小元素往后数 k 步
当 k 很小时（比如 k = 1），几乎瞬间返回，根本不碰右子树。
class Solution {
// 状态放在类上，所有递归层共享同一份
private var count = 0 // 已经数过几个节点
private var result = 0 // 答案
/**
* 递归中序版
*
* 时间复杂度 O(H + k)（靠剪枝实现；不剪枝就是 O(n)）
* 空间复杂度 O(H)：递归栈
*/
fun kthSmallest(root: TreeNode?, k: Int): Int {
// ⚠️ 用成员变量必须在入口重置，否则同一实例调用两次会带上次的残留
count = 0
result = 0
inorder(root, k)
return result
}
private fun inorder(node: TreeNode?, k: Int) {
if (node == null) return
inorder(node.left, k) // ① 左
// ② 根
// 剪枝 1：左子树里已经找到答案了（count 已达 k），当前节点不能再计数，直接回退。
// 这一句会让所有还没返回的递归层像多米诺一样连续 return。
if (count == k) return
count++
if (count == k) {
result = node.`val` // 我就是第 k 小
return // 剪枝 2：不必再进右子树
}
inorder(node.right, k) // ③ 右
}
}
LeetCode 这题带一个进阶问题：
▎ 如果 BST 经常被修改（插入/删除），并且你需要频繁查找第 k 小的值，如何优化？
上面的做法每次查询都是 O(H + k)，查一万次就重复走一万遍。答案是给节点增加一个字段：
class AugmentedNode(var val: Int) {
var left: AugmentedNode? = null
var right: AugmentedNode? = null
var size = 1 // 🔑 以自己为根的子树中，节点的总个数（含自己）
}
有了 size，查询就变成在树上做一次二分下降，完全不用遍历：
站在任意节点，设 leftSize = 左子树的节点数。那么这个节点在它自己这棵子树的中序序列里，排第 leftSize + 1 位。于是三种情况：
/** * 借助子树大小信息，O(h) 查询第 k 小 —— 不需要任何遍历 */ fun kthSmallest(root: AugmentedNode?, k: Int): Int { var node = root var target = k
while (node != null) {
val leftSize = node.left?.size ?: 0 // 左子树有多少个节点
when {
// 情况 1：我自己就排第 leftSize + 1 位，正好是要找的
target == leftSize + 1 -> return node.`val`
// 情况 2：要找的名次比我靠前 → 一定在左子树里，名次不变
target <= leftSize -> node = node.left
// 情况 3：要找的名次比我靠后 → 在右子树里。
// 左子树的 leftSize 个 + 我自己 1 个都比它小，要从名次里扣掉
else -> {
target -= leftSize + 1
node = node.right
}
}
}
return -1
}
代价： 每次插入/删除时，要顺着路径更新沿途所有节点的 size，这也只是 O(h)。
效果： 查询从 O(H + k) 降到 O(h)，且和 k 的大小无关（k = n 时也一样快）。这种"节点上挂统计信息"的树叫 Order Statistic Tree（顺序统计树），配合 AVL/红黑树保持平衡后，h = O(log n)，插入、删除、查第 k 小全都是 O(log n)。
复杂度
- 时间复杂度:
- 空间复杂度:
- 邮箱 ：charon.chui@gmail.com
- Good Luck!