LeetCode刷题笔记第98题：验证二叉搜索树

想法一：
要满足题中二叉树的要求，需要判断根节点是否大于于左节点并小于右节点。递归判断二叉树中的每个节点，当满足要求时最终返回True，当某个节点的值不满足时则返回False。代码及注释如下。

# 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: TreeNode) -> bool:    
        # 定义函数BFS比较根节点与左右子节点的大小
        def BFS(root, left, right):
            # 当根节点为空时说明上一个节点为叶子节点，判断结束，返回True
            if root is None:
                return True
            # 如果根节点的值在左右数值之间则满足条件继续判断其左右子树
            if left < root.val < right:
                return BFS(root.left, left, root.val) and BFS(root.right, root.val, right)
            else:
                return False
        # 将一开始左右的数值定义为负正无穷大
        return BFS(root, -float('inf'), float('inf'))

想法二：
判断满足题目所述要求的二叉树，通过中序遍历形成的序列是升序序列，判断相应位置的大小关系得到最终的结果。代码及注释如下。

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # 建立一个栈和一个无穷小值inorder为后续判断大小做准备
        stack, inorder = [], float('-inf')
        
        # 当栈或根节点存在时循环继续
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            # 弹出树中左子树中最左的叶子节点    
            root = stack.pop()
            # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            # 判断根节点与其左右节点的大小
            if root.val <= inorder:
                return False
            # 若上述成立则将其赋值给inorder进行下一轮的判断
            inorder = root.val
            # 判断根的右节点
            root = root.right

        return True