经典150题 - 二叉搜索树

530. 二叉搜索树的最小绝对差

var getMinimumDifference = function (root) {
    let min = Infinity
    let pre = undefined
 
    const dfs = (node) => {
        if(!node) return
        dfs(node.left)
        if(pre) min = Math.min(min, node.val - pre.val)
        pre = node
        dfs(node.right)
    }
 
    dfs(root)
    return min
};

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
    }
};

98. 验证二叉搜索树

var isValidBST = function (root) {
    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)
};

相关笔记

• 树与二叉树基础
• 二叉树其他题目
• 二叉树专题