二叉搜索树中第 K 小的元素
Kth Smallest Element in a BST
返回二叉搜索树中第 k 小的节点值（k 从 1 开始）。
在力扣中练习题目描述
给定一个二叉搜索树的根节点 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 <= 1040 <= Node.val <= 104
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
解题思路
中序迭代 · 提前停止
BST 中序升序，数到第 k 个就停
BST 的中序遍历是升序序列，所以“第 k 小”就是中序访问到的第 k 个节点。不需要把所有节点存下来。
沿用第 94 题的迭代中序模板：沿左链压栈，弹出即访问，然后转向右子树。每弹出一个节点就把计数加一，等于 k 时立刻返回。
k=5；中序遍历到第 5 个节点就停，不需要遍历完整棵树。
自拟树有 9 个节点，k=5。前四个是 1、3、4、6，第五个是 7；找到后右半边 10、13、14 都不会再访问。
沿左链压栈 6 → 4；最小的未访问节点在栈顶。
- 8
- 6
- 4← top
时间 O(h + k)：最多压入 h 个祖先，再访问 k 个节点；空间 O(h)。如果每次插入/删除后频繁查询第 k 小，可以改用在节点里维护子树大小，做到 O(h)。
易错点
- 用前序或后序计数：得到的不是升序序列。
- 找到后继续遍历：结果正确但多做无用功，也可能覆盖答案。
- 计数器从 0 开始却用 count == k 在弹出前判断：会错过第 k 个。
中序递归 · 全局计数
递归中序，数到 k 就记录答案
逻辑同样简洁，但递归深度为 h，且提前返回要靠额外标记；迭代版更容易在 k 处停。
递归中序的访问顺序天然升序：先递归左子树，再访问当前节点，最后递归右子树。
用一个成员计数器和一个答案变量。访问节点时先自增，若等于 k 就记录答案并返回；之后的递归通过 ans != -1 提前结束。
它的可读性很好，但需要额外状态来终止递归；如果树退化成链，递归深度为 n。
- 1递归左子树。
- 2访问当前节点，计数器加一。
- 3等于 k 时记录答案并终止。
- 4递归右子树。
易错点
- 找到答案后没有终止标记：仍会继续遍历整棵树。
- 先访问再递归左子树：顺序变成根-左-右，不再是升序。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
root = [8,3,10,1,6,null,14,null,null,4,7,13]，k = 5k=5；中序遍历到第 5 个节点就停，不需要遍历完整棵树。
查看 C++ 代码
延伸阅读
- BST 的中序序列就是排序结果，很多“第 k 小/第 k 大”都可以套这个模板。
- 第 k 大可以改成“右-根-左”的逆中序，或者先求总节点数再转换。