98_验证二叉搜索树

类型：树

验证二叉搜索树 💛

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

❓ 验证一棵二叉树是不是搜索树。

可以用前序、中序、后序三种方法来做，请看 leetcode 提交记录。

💡 中序遍历

一棵二叉搜索树的中序遍历结果应该是递增序列。

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # 对搜索树进行中序遍历，其结果必然是有序的
        if not root:
            return False

        res = []

        def traverse(node):
            if not node:
                return
            traverse(node.left)
            res.append(node.val)
            traverse(node.right)

        traverse(root)
        return all(res[i] < res[i + 1] for i in range(len(res) - 1))

时间复杂度：O(n)，空间复杂度：O(n)

💡 递归

对于搜索树的任意结点来说，其左子树的结点值均小于该结点，其右子树的结点值均大于该结点。

我们设计一个函数 check(root, lower, upper) 来检查以 root 为根的子树是否结点值均在 (l, r) 范围内（开区间）。一开始的时候，我们的范围应该是 (-inf, +inf)。

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def check(node, lower = float('-inf'), upper = float('inf')) -> bool:
            if not node:
                return True

            val = node.val
            if val <= lower or val >= upper:
                return False

            if not check(node.right, val, upper):
                return False
            if not check(node.left, lower, val):
                return False
            return True

        return check(root)

时间复杂度：O(n)，空间复杂度：O(n)