给定一个二叉搜索树的根节点 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 小的值，你将如何优化算法？

首先想到中序遍历，遍历结果是有序的

只需要记录当前遍历了多少个元素即可，当cur==k可以返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int ans = 0;
    bool flag = false;
    int kthSmallest(TreeNode *root, int k) {
        int cur = 0;
        order(root, cur, k);
        return ans;
    }
    void order(TreeNode *root, int &cur, int k) {
        if (root == nullptr || flag)
            return;

        order(root->left, cur, k);
        cur++;
        if (cur == k) {
            ans = root->val;
            flag = true;
            return;
        }
        order(root->right, cur, k);
    }
};