leetcode每日一练-第98题- 验证二叉搜索树

**LeetCode 每日一练 - 第98 题: 验证二叉搜索树**

### 题目描述给定一个二叉树的根节点 `root`，判断该树是否是二叉搜索树。

**注意:** 这个问题的定义指的是输入为整数的二叉树所有节点的值都严格单调不下降。

### 示例1:

输入: [2,1,3]
输出: true

### 示例2:

输入: [5,1,4,null,null,3,6]
输出: false

### 示例3:

输入: []
输出: true

### 示例4:

输入: [10,5,15,3,7,12,18]
输出: true

### 示例5:

输入: [-10,-5,0,5,10]
输出: false

### 思路要验证一个二叉树是否是二叉搜索树，我们需要检查每个节点的值是否满足单调不下降的条件。我们可以使用中序遍历（Inorder Traversal）来实现这一点。

中序遍历是一种遍历二叉树的方式，先访问左子树，然后访问根节点最后访问右子树。如果一个二叉树是二叉搜索树，那么中序遍历得到的值序列一定是严格单调不下降的。

###代码实现

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isValidBST(root):
 """
 验证二叉搜索树 :param root: 二叉树的根节点 :return: True 如果是二叉搜索树，False 否则 """
 def inorder_traversal(node, min_val=float('-inf'), max_val=float('inf')):
 # 如果当前节点为空，则返回True if not node:
 return True # 如果当前值不在[min_val, max_val]范围内，则返回False if not min_val < node.val < max_val:
 return False # 递归检查左子树和右子树 return (inorder_traversal(node.left, min_val, node.val) and inorder_traversal(node.right, node.val, max_val))
 return inorder_traversal(root)

###代码注释* `isValidBST` 函数是入口函数，负责验证给定的二叉树是否是二叉搜索树。
* `inorder_traversal` 是一个递归函数，用于中序遍历二叉树。它接受三个参数：当前节点、最小值和最大值。
* 如果当前节点为空，则返回True，因为空树是二叉搜索树。
* 如果当前值不在[min_val, max_val]范围内，则返回False，因为该值违反了单调不下降的条件。
* 递归检查左子树和右子树，直到所有节点都被访问完毕。

### 测试用例

# 示例1:
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
print(isValidBST(root)) # True# 示例2:
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(6)
print(isValidBST(root)) # False# 示例3:
print(isValidBST(None)) # True

### 总结本题目要求验证一个二叉树是否是二叉搜索树。我们使用中序遍历来实现这一点，并且递归检查每个节点的值是否满足单调不下降的条件。如果所有节点都通过了检查，则返回True，否则返回False。