验证二叉搜索树

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

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

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

在这里插入图片描述

输入：root = [2,1,3]
输出：true
示例 2：

在这里插入图片描述

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在 $1, 10^4]$ 内
$2^{31} <= Node.val <= 2^{31} - 1$

思想来自官方解说。这个问题比较容易想到递归，但是递归过程中需要注意一个问题，不能只检查当前节点跟左右两个子节点的大小关系，因为BST要求当前节点的左子树的节点都要小于当前节点，这种可能出现不符合BST规则的地方主要存在于：遍历左子树的右子树时，需要右子树大于父节点同时小于爷爷节点；遍历右子树的左子树时，需要左子树小于父节点同时大于爷爷节点。

递归遍历是深度优先遍历，是自上而下的遍历，遇到不符合的节点会提前返回，而不往下继续遍历。

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:
        def helper(node, lower=None, upper=None) -> bool:
            if not node:
                return True

            val = node.val
            if (lower is not None and val <= lower) or (upper is not None and val >= upper):
                return False

            #左右子树的遍历顺序没有要求
            if not helper(node.right, val, upper):
                return False
            if not helper(node.left, lower, val):
                return False
            return True

        return helper(root)