题目
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid 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.
解题思路
使用DFS遍历树，遍历的时候向下传上下界，根据上下界判断是否符合要求
代码
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def check(root, l, r):
if root == None:
return True
val = root.val
if val <= l or val >= r:
return False
return check(root.left, l, val) and check(root.right, val, r)
return check(root, float('-inf'), float('inf'))
