[LeetCode]题解（python）：098 Validate Binary Search Tree

题目来源

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

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

题意分析

Input:二叉树

Output:boolean值

Conditions:检验一个二叉树是不是有效的二叉搜索树

题目思路

注意到，每层的最大最小约束都是不一样的，所以采用dfs的思想，不断更新最大最小值。在python中，数字可以取很大，要设大一点。

AC代码（Python）

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def validBST(self, root, min, max):
10         if root == None:
11             return True
12         if root.val <= min or root.val >= max:
13             return False
14         return self.validBST(root.left, min, root.val) and self.validBST(root.right, root.val, max)
15     def isValidBST(self, root):
16         """
17         :type root: TreeNode
18         :rtype: bool
19         """
20         return self.validBST(root, -21474836480, 21474836470)
21