一、题目描述

给定一个二叉搜索树（BST）的根节点 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 <= 10^4

• 0 <= Node.val <= 10^4

进阶

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

---

二、解题思路

核心观察：
二叉搜索树（BST）的性质：左子树 < 根 < 右子树
中序遍历（左 → 根 → 右）得到的序列是递增序列。

因此，本题本质上是：找 BST 的中序遍历序列的第 k 个元素。

---

三、解法一：递归中序遍历

1. 算法步骤

1. 递归遍历左子树

2. 访问当前节点（计数）

3. 如果计数等于 k，记录结果并返回

4. 遍历右子树

2. C 语言实现

int res;      // 存储结果
int count;    // 计数器

void inorder(struct TreeNode* root, int k) {
    if (!root) return;

    inorder(root->left, k);

    if (count >= k) return; // 找到答案后剪枝

    count++;
    if (count == k) {
        res = root->val;
        return;
    }

    inorder(root->right, k);
}

int kthSmallest(struct TreeNode* root, int k) {
    count = 0;
    res = 0;
    inorder(root, k);
    return res;
}

复杂度分析：

• 时间复杂度：O(H + k)，H 是树的高度

• 空间复杂度：O(H)，递归栈空间

---

四、解法二：迭代中序遍历

对于大树或不想用递归的场景，可以用栈模拟中序遍历。

#include <stdlib.h>

int kthSmallest(struct TreeNode* root, int k) {
    struct TreeNode* stack[10000]; // 栈
    int top = -1;

    while (root || top != -1) {
        while (root) {
            stack[++top] = root;
            root = root->left;
        }

        root = stack[top--];
        k--;
        if (k == 0) return root->val;

        root = root->right;
    }

    return -1; // 不存在
}

复杂度分析：

• 时间复杂度：O(H + k)

• 空间复杂度：O(H)

---

五、进阶优化：Order Statistic Tree

如果 BST 频繁修改且需要频繁查询第 k 小元素，递归/迭代每次都遍历会很慢。

优化方法：
在每个节点增加一个 size 属性，表示该节点子树的节点数。

struct TreeNode {
    int val;
    int size; // 子树节点数
    struct TreeNode* left;
    struct TreeNode* right;
};

• 查询第 k 小：O(log n)

• 插入/删除：维护 size → O(log n)

• 核心思路：

  1. 当前节点左子树大小 = L

  2. 如果 k <= L → 去左子树查

  3. 如果 k == L + 1 → 当前节点就是答案

  4. 如果 k > L + 1 → 去右子树查 k - (L + 1)

这种方式类似 顺序统计树（Order Statistic Tree），在面试中是加分点。

---

六、总结

1. 核心思路：BST 中序遍历递增 → 找第 k 个元素

2. 解法选择：

   • 普通查找 → 递归或迭代中序遍历

   • 面试加分 → 维护子树大小优化到 O(log n)

3. 注意点：

   • 找到答案后可以提前剪枝，避免无用遍历

   • 迭代写法更接近实际工程