专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
之前写过一篇文章，结果有不少网友口味比较重，喜欢这种回答的方式，问我在哪找的，今天终于找到了，使用的是天工AI，下面是我让它回复的一个问题。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第98：验证二叉搜索树。
问题描述
来源：LeetCode第98题
难度：中等
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
1，节点的左子树只包含小于当前节点的数。
2，节点的右子树只包含大于当前节点的数。
3，所有左子树和右子树自身必须也是二叉搜索树。
示例1：
输入：root = [2,1,3] 输出：true
示例2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
树中节点数目范围在[1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1
问题分析
这题让验证二叉搜索树，二叉搜索树有一个规律就是它的 中序遍历结果一定是有序的 。我们只需要把这棵树按照中序遍历的顺序遍历，然后判断遍历的结果是否是有序的即可。
这里我们没必要全部遍历，按照中序遍历的方式每次和遍历的前一个节点比较，如果不是递增的，说明它不是二叉搜索树。
JAVA：
// 前一个结点
TreeNode prev;
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
if (!isValidBST(root.left))// 递归左子树是否是二叉搜索树
return false;
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
if (prev != null && prev.val >= root.val)
return false;
prev = root;
// 递归右子树是否是二叉搜索树
return isValidBST(root.right);
}C++：
public:
// 前一个结点
TreeNode *prev;
bool isValidBST(TreeNode *root) {
if (root == nullptr)
return true;
if (!isValidBST(root->left))// 递归左子树是否是二叉搜索树
return false;
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
if (prev && prev->val >= root->val)
return false;
prev = root;
// 递归右子树是否是二叉搜索树
return isValidBST(root->right);
}Python：
def isValidBST(self, root: Optional[TreeNode]) -> bool:
prev = None # 前一个结点
def helper(node):
nonlocal prev
if node is None:
return True
if not helper(node.left): # 递归左子树是否是二叉搜索树
return False
# 访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
if prev is not None and prev.val >= node.val:
return False
prev = node
# 递归右子树是否是二叉搜索树
return helper(node.right)
return helper(root)笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴