如何求二叉搜索树中第 K 小的元素？

简化版

利用「BST 中序遍历得升序」这个性质：中序遍历，数到第 K 个访问的节点就是第 K 小。不用遍历完整棵树——数到第 K 个就可以提前停下。用迭代（栈）实现能自然地边走边计数、及时返回，O(H + K)。

详细版

递归 + 计数

int count = 0, result = 0;
int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return result;
}
void inorder(TreeNode node, int k) {
    if (node == null) return;
    inorder(node.left, k);
    if (++count == k) { result = node.val; return; }  // 数到第 k 个
    inorder(node.right, k);
}

迭代 + 提前返回（推荐）

int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }  // 压左到底
        cur = stack.pop();
        if (--k == 0) return cur.val;      // 第 k 个，立即返回
        cur = cur.right;
    }
    return -1;
}

迭代版好处：数到第 K 个立刻 return，不必遍历剩下的节点，时间是 O(H + K)（H 是树高，先下降到最左，再弹出 K 个）。

完整版教学

一、核心：中序遍历的第 K 个

这题几乎是「BST 中序有序」性质的直接应用。中序遍历（左根右）产出升序序列，那么第 K 个被访问的节点就是第 K 小的元素。所以问题就是「中序遍历，计数到 K」。理解了这点，代码只是实现细节。

二、为什么迭代版更优

递归版如果不做提前返回控制，会走完整棵中序遍历，O(n)。迭代版天然支持「数到就停」：用栈显式地一路压左到底，然后逐个弹出（每弹出一个就是中序序列的下一个），弹到第 K 个立即返回。它只需要下降到最左（O(H)）再弹出 K 个（O(K)），所以 O(H + K)，当 K 很小时远优于 O(n)。

三、进阶：如果频繁查询第 K 小怎么办

如果同一棵树要多次查询不同的 K，每次都 O(H+K) 中序遍历不划算。优化：在每个节点里额外维护「以它为根的子树节点数」size。查询时：

设左子树大小为 L。
若 K == L + 1，当前节点就是第 K 小。
若 K ≤ L，去左子树找第 K 小。
若 K > L + 1，去右子树找第 K - L - 1 小。

这样单次查询降到 O(H)（平衡时 O(log n)），代价是插入/删除时要维护 size 字段。这是「BST 增强节点信息」的典型手法，也是顺序统计树的思路。

四、第 K 大怎么办

对称地，第 K 大就是「反向中序遍历（右根左）」的第 K 个——反向中序产出降序序列。把上面代码的「先压左、再转右」改成「先压右、再转左」即可。

五、复杂度小结

中序遍历法：O(H + K) 时间（迭代提前返回），O(H) 空间。
维护子树 size 法：单次查询 O(H)，适合多次查询，但增删要维护 size。

六、常见误区与追问

考点	正确口径
单次查询	中序遍历计数到第 k 个
提前停止	计数到 k 后直接返回，不必遍历剩余节点
频繁查询	节点维护子树大小，按排名下降

inorder:
  visit left
  count += 1
  if count == k: answer = node.val
  visit right

第 K 小不是排序题，而是利用 BST 中序本来就有序。

误区：必须把所有节点放进数组再取第 k 个。 数组法可行但会多用 O(n) 空间；中序计数可以提前停止。
误区：k 从 0 开始还是 1 开始无所谓。 题目通常说第 K 小是 1-based，计数边界写错会返回前一个或后一个节点。
误区：普通二叉树也能直接中序取第 k 小。 只有 BST 的中序遍历才是升序，普通二叉树必须另行排序或用堆。
追问：第 K 大怎么做？ 反向中序右根左，计数到第 k 个即可。
追问：频繁查询如何优化？ 在每个节点维护左子树大小或整棵子树大小，按排名决定向左、返回当前或向右。
追问：复杂度如何表达？ 单次中序最坏 O(n)，提前停止时访问 O(k+h) 量级；增强版查询可到 O(h)。

七、加强记忆

BST 第 K 小 = 中序遍历的第 K 个（中序得升序）。迭代法一路压左、逐个弹出计数，数到第 K 个立即返回，O(H + K)、不必遍历全树。频繁查询就给每个节点维护子树大小 size，靠「左子树大小」决定往左/命中/往右，单次 O(H)。第 K 大则用反向中序（右根左）。

简化版

详细版