【leetcode】230. 二叉搜索树中第K小的元素

leetcode-230.png

var kthSmallest = function(root, k) {
    // 获取 root左边节点的 所有节点数量
    let leftNodeNum = cntTreeNode(root.left)
    // 如果左边有 k - 1 个节点，那么第k个节点肯定是 root 节点
    if(leftNodeNum === k - 1){
        return root.val
    }
    // 如果左边节点的数量 >= k那就要到左边的节点上进一步进行寻找
    // 再次调用 kthSmallest 就好了
    if(leftNodeNum >= k){
        return kthSmallest(root.left, k)
    }
    // 此时就是转向 右边节点寻找了，左边的节点数量 < k
    // 那么就 左边节点数量 + 根节点 = leftNodeNum + 1
    // 寻找右边的 第 k - (leftNodeNum + 1) 即可
    return kthSmallest(root.right, k - leftNodeNum - 1)
};
// 计算树的节点数量
var cntTreeNode = function(root){
    if(!root){
        return 0
    }
    return cntTreeNode(root.left) + cntTreeNode(root.right) + 1
}

中序遍历

这里要搞明白的一点就是，这是一个二叉搜索树
其性质就是，节点的值满足：左 < 根 < 右
整个二叉搜索树按照中序遍历下来，肯定会满足 所有的节点按照从小到达的顺序排列，所以这里在中序遍历的时候加上一个计数器cnt，当cnt满足 cnt === k的时候，此时就是第k小的数了

var kthSmallest = function(root, k) {
    let cnt = 0
    let res = null
    var inorder = function(root){
        if(!root || res !== null){
            return
        }
        inorder(root.left)
        cnt++
        if(cnt === k){
            res = root.val
            return
        }
        inorder(root.right)
    }
    inorder(root)
    return res
};