230

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

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

• inorder - iteration
• inorder - recursion
• countNode
• priority queue
• avl

inorder

• iteration

let kthsmall = function (root,k){
    let stack = [];
    while(root !== null || stack.length){
        while(root !== null){
            stack.push(root);
            root = root.left
        }
        root = root.pop();
        --k;
        if(k==0){
            break;
        }
        root = root.right;
    }
    return root.val;
}

• recursion

to be  continued

countnode

function countNode (root) {
    if(root == null) return 0;
    let l = countNode(root.left);
    let r = countNode(root.right);
    return l+r+1;
}
let kthSmall =  (root,k)=>{
    let c = countNode(root.left);
    if(c == k-1)return root.val;
    else if(c<k-1) return kthSmal(root.right,k-c-1);
    return kthSmall(root.left,k)
}