题解 | #二叉搜索树的第k个节点#

原来可以中序遍历求解啊，没想到哈哈。

• 用的递归，先判断左右子树的节点数，k与之比较
• 当小于等于左子树节点数时，目标节点就是左子树的第k小；
• 当k等于左子树节点数+1时，目标节点就是根节点；
• 当k大于左子树节点+1时，目标节点为右子树的第（k-左子树节点数-1）小。

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param proot TreeNode类 
 * @param k int整型 
 * @return int整型
 */
function KthNode( proot ,  k ) {
    // write code here
  //  树的节点总数
  
    let nodeNumber = nodeNum(proot);
  
    if (k > nodeNumber || ! proot) {
        return -1;
    }
  
  //  左子树节点数
  
    let nodeNumberLeft = nodeNum(proot.left);
  
  //  右子树节点数
  
    let nodeNumberRight = nodeNumber - nodeNumberLeft - 1;
  
    if (k <= nodeNumberLeft) {
        return KthNode(proot.left, k);
      
    } else if (k == nodeNumberLeft + 1) {
        return proot.val;
      
    } else {
        return KthNode(proot.right, k - nodeNumberLeft - 1);
    }
  
    return -1;
}
//计算树的节点数
function nodeNum (proot) {
  
    if (!proot) {
        return 0;
    }
  
    return nodeNum(proot.left) + nodeNum(proot.right) + 1;
  
}
module.exports = {
    KthNode : KthNode
};