验证二叉搜索树 前序 中序 后序的三种解法 - 灵神视频总结

这节课用三种方法来验证一颗二叉树是否是搜索树。

递归的基础知识：

1. 看到递归就晕？带你理解递归的本质！-- 灵神视频总结-CSDN博客
2. 如何灵活运用递归？- 灵神视频总结-CSDN博客

98. 验证二叉搜索树

二叉搜索树的定义：

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

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

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

分析：

二叉搜索树 左子树的值都比当前节点的值要下。 假设当前节点的值 范围是 (a,b), 当前节点值为x，

那么左子树的节点值范围为 (a, x) 开区间。右子树的节点值的范围为 （x, b) 开区间。

递归解决，我们假定root节点的范围为 (-inf, inf)

先遍历左子树，如果左子树是一个二叉搜索树，且节点值比 当前节点要小。

然后再遍历右子树，如果右子树是一个二叉搜索树，且节点值比当前节点要大。

当前节点 比 left 都边界大， 比right 边界小。

代码

# 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], left = -inf, right = inf) -> bool:
        if root is None : 
            return True 
        x = root.val 
        return left < x < right and self.isValidBST(root.left, left, x) and self.isValidBST(root.right, x, right)

第二种方法，如果按照中序遍历，二叉搜索树可以获得严格的递增数列。

只需要比较当前节点按照左<中< 右 的顺序遍历，如果当前节点 > 中，直接返回false。

1. 边界条件
2. 先判断左子树，如果不是二叉搜索树返回False， 如果当前节点小于等于前一节点，返回False。把pre 设置为当前节点，接着遍历右子树。

代码：

# 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:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root :
            return True 
        if not self.isValidBST(root.left):
            return False 
        x = root.val 
        if x <= self.pre :
            return False
        self.pre = x 
        return self.isValidBST(root.right)

后序遍历

先遍历左右子树，然后返回左右子树的边界，然后只要当前节点大于左子树返回的右边界，小于右子树返回的左边界。

边界条件很重要： 如果是空节点，我们返回的 inf, -inf ， 最终判断一个二叉树是否是搜索二叉树，就要判断它的max 是不是-inf ，函数返回的是啥 左边的最小值，和 右边的最大值。

代码

# 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:
        def dfs(node):
            if node is None:
                return inf, -inf
            l_min, l_max = dfs(node.left)
            r_min, r_max = dfs(node.right)
            x = node.val 
            if x <= l_max or x >= r_min :
                return -inf, inf
            return min(x, l_min), max(x, r_max)
        return dfs(root)[1] != inf

  系列文章 

1.  三数之和 - 灵神视频总结。-CSDN博客 
2. 盛最多水的容器 接雨水 - 灵神视频总结-CSDN博客
3. 滑动窗口 模版 - 灵神视频总结-CSDN博客
4. 二分查找 红蓝染色法 - 灵神视频总结-CSDN博客
5. 二分查找 数组峰值 旋转排序数组 - 灵神视频总结-CSDN博客
6. 反转链表 K个一组反转链表 - 灵神视频总结-CSDN博客
7. 环形链表 快慢指针 奇偶链表 重排链表 -- 灵神视频总结-CSDN博客
8. 删除链表重复节点 - 灵神视频总结-CSDN博客
9. 看到递归就晕？带你理解递归的本质！-- 灵神视频总结-CSDN博客
10. 如何灵活运用递归？- 灵神视频总结-CSDN博客