专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近一网友晒出了华为在上海青浦的工作餐，被网友调侃太贵了，看到第一眼的时候我感到很诧异，倒不是觉得它贵，而是觉得工作餐不应该是免费的吗？我之前工作有两家公司也都是提供工作餐，一家是在手机上自己点，午饭的时候会打包好统一送过来，还一种是送过来我们自己去盛的，都是免费的。即便是在十多年前我在寒暑假打工的的时候，工作餐也都是免费的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是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

问题分析

这题让验证二叉搜索树是否有效，我们知道二叉搜索树有一个重要的特性就是它的 中序遍历结果一定是有序的（递增的） ，我们对二叉树进行中序遍历，如果结果是递增的，那么它就是一颗有效的二叉搜索树，否则不是二叉搜索树。

这里我们没必要遍历二叉树的全部节点，按照中序遍历的方式每次和遍历的前一个节点比较，如果当前节点的值小于等于前一个节点的值，说明不是递增的，不是二叉搜索树，直接返回false即可。

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算法文档 。