98.md

题目地址

https://leetcode-cn.com/problems/validate-binary-search-tree/

解答1

def isValidBST(root):
    """
        验证二叉搜索树(非最优解)

        递归
    """

    def helper(node, lower, upper):
        if not node:
            return True

        if lower < node.val < upper:
            return helper(node.left, lower, node.val) and helper(node.right, node.val, upper)
        else:
            return False

    return helper(root, float('-inf'), float('inf'))

解答2

def isValidBST(root):
    """
        验证二叉搜索树(非最优解)

        中序遍历
    """
    ans, stack, node = [], [], root

    while node is not None or stack:
        while node is not None:
            stack.append(node)
            node = node.left

        if stack:
            node = stack.pop()
            ans.append(node.val)
            node = node.right

    if len(ans) < 2:
        return True
    for i in range(len(ans) - 1):
        if ans[i] >= ans[i + 1]:
            return False

    return True

解答3

def isValidBST(root):
    """
        验证二叉搜索树

        mirrors算法
    """
    a = c = 0
    while root is not None:
        if root.left is None:
            if c != 0 and a >= root.val:
                return False
            c = 1
            a = root.val
            root = root.right
        else:
            t = root.left
            while t.right and t.right != root:
                t = t.right
            if t.right is None:
                t.right = root
                root = root.left
            else:
                t.right = None
                if c != 0 and a >= root.val:
                    return False
                c = 1
                a = root.val
                root = root.right
    return True

解答4

def isValidBST(root):
    """
        验证二叉搜索树

        中序遍历
    """
    last = float("-inf")

    if root is None:
        return True
    if isValidBST(root.left):
        if last < root.val:
            last = root.val
            return isValidBST(root.right)
    return False

解答5

class Solution:
    def isValidBST(self, root):
        """
            验证二叉搜索树

            中序遍历
        """
        self.prev = None
        return self.helper(root)

    def helper(self, root):
        if root is None:
            return True
        if not self.helper(root.left):
            return False
        if self.prev and self.prev.val >= root.val:
            return False
        self.prev = root
        return self.helper(root.right)

解答6

def isValidBST(root):
    """
        验证二叉搜索树

        中序遍历
    """
    result = []

    def inorder(root, result):
        if root:
            inorder(root.left, result)
            result.append(root.val)
            inorder(root.right, result)

    inorder(root, result)

    return sorted(set(result)) == result