【代码随想录day20】验证二叉搜索树

**代码随想录 Day20: 验证二叉搜索树**

在前面的文章中，我们讨论了二叉搜索树（Binary Search Tree）的基本概念。今天，我们将重点讨论如何验证一个给定的二叉树是否是二叉搜索树。

## 一、什么是二叉搜索树二叉搜索树是一种特殊的二叉树，每个结点最多有两个子结点（左孩子和右孩子），且每个结点的值都满足以下条件：

* 左子树中的所有值都小于该结点的值。
* 右子树中的所有值都大于该结点的值。

## 二、如何验证二叉搜索树要验证一个给定的二叉树是否是二叉搜索树，我们可以使用中序遍历（Inorder Traversal）来检查每个结点的值是否满足上述条件。具体步骤如下：

1. 首先，中序遍历二叉树，得到一个有序数组。
2. 然后，对于这个有序数组中的每个元素，我们检查它是否满足以下条件：
* 如果当前元素是左子树中的最大值，则该元素的右孩子应该为 NULL。
* 如果当前元素是右子树中的最小值，则该元素的左孩子应该为 NULL。

## 三、代码示例下面是一个 Python代码示例，用于验证二叉搜索树：

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isValidBST(root):
 """
 验证给定的二叉树是否是二叉搜索树。
 Args:
 root: 二叉树的根结点。
 Returns:
 True 如果二叉树是二叉搜索树，False 否则。
 """
 def inorder(root):
 # 中序遍历二叉树 if not root:
 return []
 return inorder(root.left) + [root.val] + inorder(root.right)
 values = inorder(root)
 for i in range(len(values)):
 # 检查每个结点的值是否满足条件 if i >0 and values[i-1] >= values[i]:
 return False return True# 测试用例root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

print(isValidBST(root)) # Output: Trueroot = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(7)
root.left.right = TreeNode(6)
root.right.left = TreeNode(4)

print(isValidBST(root)) # Output: False