二叉搜索树

1. 验证二叉搜索树

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

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

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

• 输入：root = [2,1,3]
  输出：true
  ```python
  # 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)
  

赏

谢谢你请我吃糖果