98. 验证二叉搜索树

[Geekhyt]

原题链接

中序遍历

二叉搜索树需要满足以下三个条件：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

1. 二叉搜索树在中序遍历时得到的序列一定是升序的
2. 进行中序遍历，判断当前节点是否大于前一个节点
3. 如果比前一个大，说明满足，则继续遍历，否则直接返回 false

递归

const isValidBST = function(root) {
    let prev = -Infinity
    let result = true
    function inorder(root) {
        if (root === null) return
        inorder(root.left)
        if (root.val <= prev) {
            result = false
            return 
        }
        prev = root.val
        inorder(root.right)
    }
    inorder(root)
    return result
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

迭代

递归隐式地维护了一个栈，在迭代的时候我们需要显式地将这个栈模拟出来。

const isValidBST = function (root) {
    const stack = []
    let prev = -Infinity
    while (root || stack.length) {
        while (root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        if (root.val <= prev) {
            return false
        }
        prev = root.val
        root = root.right
    }
    return true
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

[eavan5]

这个中序递归有问题。。

[Geekhyt]

这个中序递归有问题。。

已修正