[230] 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 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 。

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

二叉搜索树，即 BST，它拥有两个特性：

1. 对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
2. 对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

从它的两个特性我们可以注意到，它与我们在快速排序完成后的树形结构是一模一样的。也就是说，二叉搜索树的中序遍历结果一定是有序的。这个特性对我们解题的思路十分有帮助。

我们需要在 BST 中找出第 K 小的元素。由于 BST 其中序遍历是有序的，因此题目就被直接简化成：输出中序遍历的第K个结果。题目就变得十分简单了。

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let res = root.val;
  traverse(root);
  return res;

  function traverse(node: TreeNode | null) {
    if (!node) return;

    traverse(node.left);
    count += 1;
    if (count === k) {
      res = node.val;
      return;
    }
    traverse(node.right);
  }
}