一、题目

1、题目描述

实现一个函数，检查一棵二叉树是否为二叉搜索树。
样例输入： [5,1,4,null,null,3,6]
样例输出： false

2、基础框架

• C语言 版本给出的基础框架代码如下：

bool isValidBST(struct TreeNode* root){
}

3、原题链接

LeetCode 98. 验证二叉搜索树
LeetCode 面试题 04.05. 合法二叉搜索树

二、解题报告

1、思路分析

根据二叉搜索树的性质，递归判定即可。记录 左子树 和 右子树 的最小值和最大值，当前树的值为val，则要求满足 左子树 的最大值 小于val，右子树 的最小值大于val。否则都不是合法的二叉搜索树。注意，空树也是二叉搜索树。

2、时间复杂度

最坏情况为在叶子结点判断出来，遍历了所有结点，时间复杂度为 $O(n)$。

3、代码详解

bool isValidBSTEx(struct TreeNode* root, int* min, int* max) {
    int lmin, lmax;
    int rmin, rmax;
    if(root == NULL) {
        return true;
    }
    if(root->left) {
        if( !isValidBSTEx(root->left, &lmin, &lmax)  ) {
            return false;             // (1)
        }
        if( lmax >= root->val ) {
            return false;             // (2)
        }
    }else {
        lmin = lmax = root->val;
    }

    if(root->right) {
        if( !isValidBSTEx(root->right, &rmin, &rmax)) {
            return false;             // (3)
        }
        if( rmin <= root->val ) {
            return false;             // (4)
        }
    }else {
        rmin = rmax = root->val;
    }
    *min = lmin;
    *max = rmax;
    return true;
}

bool isValidBST(struct TreeNode* root){
    int min =  99999999;
    int max = -99999999;
    if(root == NULL) {
        return true;                  // (1)
    }
    return isValidBSTEx(root, &min, &max);
}

• $(1)$ 左子树不满足性质；
• $(2)$ 左子树不是二叉搜索树；
• $(3)$ 右子树不满足性质；
• $(4)$ 右子树不是二叉搜索树；
• $(5)$ 空树也是二叉搜索树;

三、本题小知识

二叉搜索树就是左子树的根结点值小于当前树的根结点，右子树的根结点值大于当前树的根结点，且左右子树都是二叉搜索树，空树也是二叉搜索树。

四、加群须知

相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
那么这里，我整理了「 几十个基础算法 」的分类，点击开启：

大致题集一览：





为了让这件事情变得有趣，以及「 照顾初学者 」，目前题目只开放最简单的算法「 枚举系列 」（包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有 一半成员刷完「 枚举系列 」的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「 夜深人静写算法 」专家团的一员。
不要小看这个专家团，三年之后，你将会是别人望尘莫及的存在。如果要加入，可以联系我，考虑到大家都是学生，没有「 主要经济来源 」，在你成为神的路上，「 不会索取任何 」。
?联系作者，或者扫作者主页二维码加群，加入刷题行列吧?

?让天下没有难学的算法?
C语言免费动漫教程，和我一起打卡！?《光天化日学C语言》?
入门级C语言真题汇总?《C语言入门100例》?
几张动图学会一种数据结构?《画解数据结构》?
组团学习，抱团生长?《算法入门指引》?
竞赛选手金典图文教程?《夜深人静写算法》?