LeetCode50天刷题计划第二季（Day 7 — 验证二叉搜索树(15.00-16.00
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、题目
- 验证二叉搜索树
- 示例
- 提示：
- 二、思路
- 三、代码
前言
写代码10分钟，debug两小时
一、题目
验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
二、思路
一开始想着，对于每个根结点，检查其左右孩子是否符合要求，然后检查子树，但这种方法只能检查子树的根结点，检查不出来是否子树中所有节点都能满足条件。
因此考虑，如果使用递归的方法，需要递归地的给每个结点设置一个区间，判断结点值是否在区间内，
这个区间根据根结点的值动态变化：对于左子树，用根节点的值作为右边界；对于右子树，用根节点的值作为左边界。
注意边界条件的选择，因为题目中给的值是-231 <= Node.val <= 231 - 1，因此边界设置为了：
MIN=-pow(2,31)-1 ； MAX=pow(2,31)
就当是val都是整数吧hhhh~
三、代码
# 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:
MIN=-pow(2,31)-1 #设置边界
MAX=pow(2,31)
def isBST(root,l,r):
if(root == None ): #根结点为空
return True
if(root.val<=l or root.val>=r): #根节点值越界
return False
Left=isBST(root.left,l,root.val) #递归，
Right=isBST(root.right,root.val,r)
return Left and Right #判断
return isBST(root,MIN,MAX) #返回
