二叉搜索树

1. 验证二叉搜索树

• （98）给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

  有效 二叉搜索树定义如下：

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

输入：root = [2,1,3]
输出：true

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.pre = -inf
        return self.isBST3(root)[0] != -inf
    def isBST1(self, root, left, right): #先序遍历，传递区间
        if root is None:
            return True
        return left < root.val < right and self.isBST1(root.left, left, root.val) and self.isBST1(root.right, root.val, right)
    def isBST2(self,root):
        if root is None:
            return True
        if not self.isBST2(root.left):
            return False
        if self.pre >= root.val:
            return False
        self.pre = root.val
        return self.isBST2(root.right)
    def isBST3(self,root):
        if root is None:
            return inf, -inf
        l_min, l_max = self.isBST3(root.left)
        r_min, r_max = self.isBST3(root.right)
        if root.val <= l_max or root.val >= r_min:
            return -inf, inf
        return min(root.val, l_min), max(root.val, r_max)

赏

谢谢你请我吃糖果