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

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：

你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入：root = [3,1,4,null,2], k = 1

输出：1

示例 2:

输入：root = [5,3,6,2,4,null,null,1], k = 3

输出：3

进阶：

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

这道题其实就是考察二叉树的中序遍历。

在二叉搜索树中，第 K 小的数实际上就是二叉树中序遍历后的索引位置，因此只需要在中序遍历时判断该位置是不是第 k 个即可。

var kthSmallest = function (root, k) {
  let res = null;
  let count = k;
  function traverse(root) {
    if (!root) return null;

    traverse(root.left);

    // 中序遍历时判断
    count -= 1;
    if (count === 0) {
      res = root.val;
      return;
    }

    traverse(root.right);
  }

  traverse(root);

  return res;
};