题目

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4

思路

根据二叉搜索树的定义，中序遍历是一个升序的数组，所以二叉搜索树的第k小的节点就是中序遍历的第k个节点
为了简化不必要的遍历，使用一个索引index来标记中序遍历已经遍历过的节点个数，当index已经等于k的时候，就不再往下遍历了
简单的中序遍历无法判断是否找到节点了，需要将找到的节点层层返回到根节点，然后最后返回

注意：index从1一开始，表示第一个，不从0开始。因为k表示第k小的数字，从1开始

代码

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function KthNode(pRoot, k) {
  // write code here
  if (!pRoot || !k) return null
  let index = 1
  function mid (pRoot, k) {
    if (pRoot) {
      let node = mid(pRoot.left, k)
      if (node) return node
      if (index === k) return pRoot
      index++
      node = mid(pRoot.right, k)
      if (node) return node
    }
    return null
  }
  return mid(pRoot, k)
}