98. 验证二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree/

解法一：中序遍历后判断

根据二叉搜索树的性质。中序遍历，将结果记录在data，再遍历data，看是否是升序，是则符合。

边界：树空，或者只有根节点，这两者都不进入循环

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.data = []
        self.inorder(root)
        for i in range(len(self.data)-1):
            if self.data[i] >= self.data[i+1]:
                return False    #不符合升序
        return True
    
    def inorder(self, root):    #中序遍历
        if not root:
            return
        self.inorder(root.left)
        self.data.append(root.val)
        self.inorder(root.right)

改进：遍历之后先将data转成set（排除重复项，二叉搜索树中不应该有重复），再排序后与原data比较，若相等则符合

if self.data == sorted(list(set(self.data))):
	return True
else:
	return False

解法二：遍历中判断

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def helper(root, lower, upper):    #参数为根，上界，下界
            if not root:    #为空不参与比较，返回真
                return True
            val = root.val
            if val <= lower or val >= upper:    #超界
                return False
            #递归左子树
            #上界为当前根，下界不变
            if not helper(root.left, lower, val):    
                return False
            #递归右子树
            #下界为当前根，上界不变
            if not helper(root.right, val, upper):                
                return False
            return True    #全部通过返回真
        #初始根不需要比较
        return helper(root, -sys.maxsize, sys.maxsize)

2021.10.22

要在递归中加入上下界参数，将其传递下去比较，否则root比左子大，不一定能保证root比左子的右子大

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def helper(root, lower ,upper):
            if root == None:
                return True
            val = root.val
            if val >= upper or val <= lower:
                return False
            return helper(root.left, lower, val) and helper(root.right, val, upper)
        return helper(root, -sys.maxsize, sys.maxsize)