98. 验证二叉搜索树(5月5日每日一题)
难度中等546收藏分享切换为英文关注反馈
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
思路一(递归法设置最大最小值)
对于一棵二叉搜索树,其左子树下所有的值一定小于根结点的值,右子树下所有的值一定大于根结点的值.
有了这个条件,我们就可以通过对每一个结点设置一个上下界,动态维护上下界的大小来判断某个结点是否符合二叉搜索树。
例如：
一个对于一个root，其值为val，而其上下界分别为max与min，执行以下步骤
1. if min < val < max
2. if min < 左子树 < val
3. if val < 右子树 < max
如果以上条件都满足， 则该root为二叉搜索树
- python代码
class Solution:
def isValidBST(self, root: TreeNode, mn=float('-inf'), mx=float('inf')) -> bool:
# 给原题的function加两个有默认值的参数，并不影响其用原来的方法调用
if not root:
return True
if root.val >= mx or root.val <= mn:
return False
if not self.isValidBST(root.left, mn, root.val):
return False
if not self.isValidBST(root.right, root.val, mx):
return False
return True
思路二（中序遍历为升序）
对于一棵二叉搜索树，其中序遍历的结果一定为升序，所以可以通过对该二叉树进行中序遍历，若出现降序，则返回false。
- python代码
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
self.pre = float('-inf')
self.flag = True # 返回值
def inTravel(root):
if not root or not self.flag:
return
inTravel(root.left)
if root.val <= self.pre:
self.flag = False
return
self.pre = root.val
inTravel(root.right)
inTravel(root)
return self.flag
