二叉搜索树的第k个节点

题目描述

示例

示例1

输入：
{5,3,7,2,4,6,8},3
返回值：
4

示例2

输入：
{},1
返回值：
-1

代码

代码1 使用中序遍历（左根右）

/*
中序遍历 左根右
二叉搜索树使用中序遍历后，最终的结果正好是从小到大排列的
然后找出第K个值即可
*/
function KthNode( proot ,  k ) {
    if(!proot || k===0) return -1
    
    let resultArr = [] // 中序遍历后保存的值
    
    // 中序遍历二叉搜索树，递归
    function midOrder(root){
        // 终止条件，遍历到头了
        if(!root) return
        
        // 中序遍历，左根右
        midOrder(root.left)
        resultArr.push(root.val)
        midOrder(root.right)
    }
    // 调用一下
    midOrder(proot)
    
    if(resultArr.length < k) return -1
    return resultArr[k-1]
}

时间复杂度O(n)：遍历的节点数

空间复杂度O(n)：递归栈内存占用的空间

题目来源

JZ54 二叉搜索树的第k个节点