樹---二叉搜索樹的第K個節點

給定一棵二叉搜索樹，請找出其中的第k小的結點。例如， （5，3，7，2，4，6，8）    中，按結點數值大小順序第三小結點的值為4。

分析：二叉搜索樹就是每個節點X，大於其左子樹的值，小於其右子樹的值，其中序排序是遞增的。使用中序遍歷，每遍歷一個節點，k-1,直到k減到1，即為第K小的節點

/* function TreeNode(x) {

    this.val = x;

    this.left = null;

    this.right = null;

} */

function KthNode(pRoot, k) {

  if (pRoot === null || k === 0) {

    return null;

  }

  // 為了能追蹤k，應該把KthNodeCore函數定義在這裡面，k應該在KthNodeCore函數外面

  function KthNodeCore(pRoot) {

    let target = null;

    if (pRoot.left !== null) {

      target = KthNodeCore(pRoot.left, k);

    }

    if (target === null) {

      if (k === 1) {

        target = pRoot;

      }

      k--;

    }

    if (target === null && pRoot.right !== null) {

      target = KthNodeCore(pRoot.right, k);

    }

    return target;

  }

  return KthNodeCore(pRoot);

}