leetcode-98

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解法

中序遍历

分别对示例1采用先序、中序遍历，结果如下：

先序：2 1 3
中序：1 2 3

分别对示例2采用先序、中序遍历，结果如下：

先序：5 1 4 3 6
中序：1 5 3 4 6

对比可以发现，中序是升序的即为真。

代码如下：

class Solution:
    def inorder(self,root:TreeNode,res):
        if not root:
            return 
        self.inorder(root.left,res)
        # print(root.val)
        res.append(root.val)
        self.inorder(root.right,res)

    def isValidBST(self, root: TreeNode) -> bool:
        res = []
        self.inorder(root,res)
        flag =  [ i for i in range(0,len(res)-1) if res[i] >= res[i+1]  ]
        if len(flag) != 0:
            return False
        else:
            return True 

官方题解，递归

如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

这启示我们设计一个递归函数helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 $(l,r)$ 的范围内（注意是开区间）。

如果 root 节点的值 val 不在 $(l,r)$ 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

根据搜索二叉树的性质，左子树的节点值小于根结点的值，所以在递归调用时，需要把上界换为根节点的值；同理在递归调用右子树时，需要下界的值换为根结点的值。

class Solution:

    def helper(self,root:TreeNode,lower,upper):
        if not root:
            return True
        elif root.val <= lower or root.val >= upper:
            return False
        else:
            return self.helper(root.left,lower,root.val) and self.helper(root.right,root.val,upper)

    def isValidBST(self, root: TreeNode) -> bool:
        return self.helper(root,float('-inf'),float('inf'))