GRD 二叉搜索树刷题

235. 二叉搜索树的最近公共祖先

var lowestCommonAncestor = function(root, p, q) {
    if(!root || root === p || root === q) {
        return root
    }
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
 
    if(left && right) {
        return root
    }
    return left || right
};

98. 验证二叉搜索树

var isValidBST = function(root) {
    if(!root) return true
    const isValid = (node, lower, upper) => {
        if(!node) return true
        if(node.val <= lower || node.val >= upper) return false
        return isValid(node.left, lower, node.val) && isValid(node.right, node.val, upper)
    }
 
    return isValid(root, -Infinity, Infinity)
};

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

var kthSmallest = function(root, k) {
    const stack = []
    while(stack.length || root) {
        while(root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        if(--k === 0) return root.val
        root = root.right
    }
};