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

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

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

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

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。
通过次数190,076提交次数580,371

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def checkChild(self, root: TreeNode):
        if root.left is None and root.right is None:
            return True, root.val, root.val

        left_min, left_max, right_min, right_max = root.val, root.val, root.val, root.val
        if root.left:
            if root.left.val >= root.val:
                return False, 1e10, -1e10
            left_flag, left_min, left_max = self.checkChild(root.left)
            if not left_flag or left_max >= root.val:
                return False, 1e10, -1e10
        if root.right:
            if root.right.val <= root.val:
                return False, 1e10, -1e10
            right_flag, right_min, right_max = self.checkChild(root.right)
            if not right_flag or right_min <= root.val:
                return False, 1e10, -1e10
        return True, left_min, right_max

    def isValidBST(self, root: TreeNode) -> bool:
        return self.checkChild(root)[0]


if __name__ == '__main__':
    s = Solution()
    root = TreeNode(5)
    root.left = TreeNode(3)
    root.right= TreeNode(6)
    root.right.left, root.right.right = TreeNode(4), TreeNode(7)
    print(s.isValidBST(root))

