首页 > 试题广场 >

判断是不是二叉搜索树

[编程题]判断是不是二叉搜索树
  • 热度指数：81751 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

例：
图1

图2

数据范围：节点数量满足 ，节点上的值满足
示例1

输入

{1,2,3}

输出

false

说明

如题面图1
示例2

输入

{2,1,3}

输出

true

说明

如题面图2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
就要上岸了的秋招人很用心头像 就要上岸了的秋招人很用心 
#include <stdbool.h>
#include <limits.h>

bool isValidBSTHelper(struct TreeNode* root, long min, long max) {
    if (root == NULL) {
        return true;
    }
    if (root->val <= min || root->val >= max) {
        return false;
    }
    return isValidBSTHelper(root->left, min, root->val) && isValidBSTHelper(root->right, root->val, max);
}

bool isValidBST(struct TreeNode* root) {
    return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}

编辑于 2024-03-31 15:49:22 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
bool isValidBSTMaxMin(struct TreeNode* root , int *Min, int *Max) {
    int LeftMin, LeftMax, RightMin, RightMax;
    bool LeftReturn, rightRturn;
    
    if(root==NULL)
        return true;
    *Min = root->val;
    *Max = root->val;
    
    if(root->left!=NULL) {
        LeftReturn=isValidBSTMaxMin(root->left, &LeftMin, &LeftMax);
        *Min = LeftMin > *Min ? *Min : LeftMin;
        *Max = LeftMax > *Max ? LeftMax : *Max;
    }
    if(root->right!=NULL) {
        rightRturn=isValidBSTMaxMin(root->right, &RightMin, &RightMax);
        *Min = RightMin > *Min ? *Min : RightMin;
        *Max = RightMax > *Max ? RightMax : *Max;
    }

    if(root->left!=NULL) 
        if((LeftReturn==false) || (LeftMax >= root->val))
            return false;
    if(root->right!=NULL) 
        if((rightRturn==false) || (RightMin <= root->val))
            return false;

    return true;
}
bool isValidBST(struct TreeNode* root ) {
    int Min, Max;
    return isValidBSTMaxMin(root, &Min, &Max);
}

编辑于 2024-03-16 18:21:14 回复(0)
C
牛客865647821号头像 牛客865647821号
2022年408真题也考察类似算法，只不过是使用数组存储二叉树。
注意，并不是左子节点比根节点小，右子节点比根节点大就叫二叉搜索树。可以通过设置一个区间，节点值不在这个区间内，就不是二叉搜索树。 
static bool isValidBST_helper(TNode *root, int lower, int upper) {
    if (root == NULL)
        return true;
    int val = root->val;
    if (val > upper||val < lower)
        return false;
    return isValidBST_helper(root->left, lower,val)&&isValidBST_helper(root->right, val,upper);
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @param root TreeNode类 
 * @return bool
 */
bool isValidBST(struct TreeNode* root) {
    if (root == NULL)
        return true;
    return isValidBST_helper(root, INT32_MIN+1, INT32_MAX-1);
}


发表于 2023-10-08 19:40:18 回复(1)
C
芸某头像 芸某
有点笨的办法
左子树找最大值
右子树找最小值
然后比对 
#include <stdbool.h>
struct TreeNode* tree(struct TreeNode* root,int flag){
    if(root == NULL){
        return NULL;
    }
    struct TreeNode* left = NULL;
    struct TreeNode* right= NULL;
    if(root->left!=NULL){
        if(root->left->val>root->val){
            return NULL;
        }
        left = tree(root->left,1);
        if(left==NULL){
            return NULL;
        }
        if(left->val>root->val){
            return NULL;
        }
    }
    if(root->right!=NULL){
        if(root->right->val<root->val){
            return NULL;
        }
        right = tree(root->right,0);
        if(right==NULL){
            return NULL;
        }
        if(right->val<root->val){
            return NULL;
        }
    }
    if(flag!=2&&left==NULL&&right==NULL){
        return root;
    }
    if(flag == 0&&left!=NULL){
        return left;
    }if(flag==1&&right!=NULL){
    return right;
    }
    return root;
}

bool isValidBST(struct TreeNode* root ) {
    if(root==NULL){
        return true;
    }
    else if(tree(root,2)==NULL){
        return false;
    }
    return true;
}


发表于 2023-09-22 17:27:43 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
bool isValidBST(struct TreeNode* root )
{
    // write code here
    static struct TreeNode*f=NULL;
    if(root)
    {
        bool h=true;
        bool l;
        bool r;
        l=isValidBST(root->left);
        if(false==l)
        {
            return false;
        }
        if(f)
        {
            if(f->val<root->val)
            {
                h=true;
            }
            else
            {
                h=false;
            }
        }
        f=root;
        if(h)
         {
            isValidBST(root->right);
         }
        else
        {
            return false;
        }
    }
    return true;
}
发表于 2023-06-29 10:46:24 回复(0)
C
又恨有爱的C头像 又恨有爱的C
int max = 0;
bool isValidBST(struct TreeNode* root )
{
    if(!root) return true;
    max = root->val;
    bool l = isValidBST(root->left);

    if(root->val < max)
    {
        return false;
    }
    else
    {
        max = root->val;
    }

    bool r = isValidBST(root->right);
    return l && r;

}
发表于 2023-05-24 20:44:57 回复(0)
C
回应我吧爱莉希雅头像 回应我吧爱莉希雅 
int max = 0;
bool turn = false;
bool check(struct TreeNode* root){
    if(!root) return true;
    bool a = check(root->left);
    if(!turn)
        turn = true, max = root->val;
    else
        if(root->val < max)
            return false;
        else
            max = root->val;
    bool b = check(root->right);
    return a&&b;
}
bool isValidBST(struct TreeNode* root ) {
    // write code here
    return check(root);
}

设置一个变量记录第一次到达中序遍历的第一个结点，以第一个结点的值作为max的初值，此后遍历的节点值只能大于之前的最大值，不能小于；如果小于就返回false
发表于 2022-10-11 20:06:05 回复(0)
C
聪敏的大白菜向光而行头像 聪敏的大白菜向光而行
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
#include <stdbool.h>
static int i=0;
void traverse(struct TreeNode* root, int *arr){
    if(root==NULL){
        return;
    }
    traverse(root->left,arr);
    arr[i++]=root->val;
    traverse(root->right,arr);
}
int treeSize(struct TreeNode*root){
    if(root==NULL){
        return 0;
    }
    return treeSize(root->left)+treeSize(root->right)+1;
}
bool isValidBST(struct TreeNode* root ) {
    // write code here
    int count=treeSize(root);
    int *arr=(int*)malloc(count*sizeof(int));
    traverse(root,arr);
    for(int k=0; k<count-1; k++){
        if(arr[k]>arr[k+1])
            return false;
    }
    return true;
}
发表于 2022-07-01 17:04:28 回复(0)
提交观点

问题信息

树
难度：
10条回答 1971浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号