首页 > 其他分享 >Check if a given binary tree is BST【2月14日学习笔记】

Check if a given binary tree is BST【2月14日学习笔记】

时间:2024-02-14 13:12:36浏览次数:28  
标签:node binary given 14 insert int data travptr root

点击查看代码
//Check if a given binary tree is BST
#include<iostream>
#define MIN -999999
#define MAX  999999

struct node {
    int data;
    node* left;
    node* right;
};

node* getnewnode(int x)
{
    node* temp = new node;
    temp->data = x;
    temp->left = temp->right = NULL;

    return temp;
}

void insert(node*& travptr, int data) {//Node*& travptr 表示 travptr 是一个引用,引用的是一个指向 Node 类型的指针

    if (travptr == NULL)
    {
        travptr = getnewnode(data);
        return;
    }
    (data > travptr->data) ? insert(travptr->right, data) : insert(travptr->left, data);
}

bool IsBST(node* root,int min,int max) {
    if(root==NULL) return true;
    if(root->data>=min&&root->data<max&&IsBST(root->left,min,root->data)&&IsBST(root->right,root->data,max))
    return true;
    return false;
}//时间复杂度:O(n)

bool isbst(node* root) {
    return IsBST(root,MIN,MAX);
}

int main()
{
    node* root = NULL;
    insert(root, 2);
    insert(root, 1);
    insert(root, 3);
    insert(root, 0);
    insert(root, 5);
    if(isbst(root)) std::cout<<"yes";
    else std::cout<<"no";
}

标签:node,binary,given,14,insert,int,data,travptr,root
From: https://www.cnblogs.com/whvivy/p/18015139

相关文章

  • Apache Ofbiz CVE-2023-51467 漏洞分析
    ApacheOfbizCVE-2023-51467漏洞分析漏洞影响范围ApacheOFBiz<18.12.10环境搭建启动docker环境vulhub-master/ofbiz/CVE-2023-51467克隆仓库,转到指定commit,用idea进行远程调试gitclonehttps://github.com/apache/ofbiz-framework.gitcdofbiz-frameworkgitche......
  • poj 1416 Shredding Company
    1416--ShreddingCompany(poj.org)#include<iostream>#include<cstring>usingnamespacestd;charnum[10];intt,max_cnt,max_sum,shred_cnt,ans[10],tmp_ans[10];//目标,最大值个数,最大值,切割次数,最后答案,临时答案voidDFS(intbegin,intnow_sum,intcnt){//切的位......
  • day14_系统服务管理
    day13作业1.如何查看系统所有环境变量,且过滤出与root相关的变量。系统全局的,本身内置的变量+用户的变量===系统全局的变量set2.如何查看⽤户个⼈的环境变量,且过滤出与root相关的变量。3.解释下PS1变量,以及如何修改使⽤PS1。请注意,linux是区分大小写的,PS1set设置变量......
  • 海亮02/14杂题
    海亮2月14日个人题单T1link题意传奇特级大师\(\mathsfE\color{red}\mathsf{ntropyIncreaser}\)有一个\(n\timesm\)的矩形纸片,她将其放置在一个平面直角坐标系中,使其左下角在\((0,0)\),右上角在\((n,m)\)位置。她每次会均匀随机选择一条平行于坐标轴、经过坐标均为......
  • WGOI R1 真夏飞焰 题解.18014664
    【题目大意】给定序列\(a\),我们定义序列\(a,b\)是「\(k\)相似」的,当且仅当对于\(a\)中每一个四元组\((l_1,r_1,l_2,r_2)\),若满足\(r_1-l_1+1=r_2-l_2+1\lek,l_2=r_1+1,a_{l_1\ldotsr_1}=a_{l_2\ldotsr_2}\),则有\(b_{l_1\ldotsr_1}=b_{l_2\ldot......
  • 力扣链表 哈希表 之 146. LRU 缓存
    请你设计并实现一个满足 LRU(最近最少使用)缓存约束的数据结构。实现LRUCache类:LRUCache(intcapacity)以正整数作为容量 capacity初始化LRU缓存intget(intkey)如果关键字key存在于缓存中,则返回关键字的值,否则返回-1。voidput(intkey,intvalue) ......
  • 14.Jenkins 参数化 Job
    参数化Job使用场景 同一个项目需要在不同环境下测试参数化Job的配置 选择参数化构建过程,选择选项参数名称填入env选项配置三个值分别:dev、test、online添加描述配置shell #判断env参数的值,如果是dev,则输出devruntimeif["$env"="dev"......
  • 迎龙年浅谈 Binary Indexed Trees
    什么是BinaryIndexedTrees?就是树状数组啦。树状数组,是一种高级数据结构,用于高效地解决某一类问题。那么这一类问题是什么呢?那么让我们一起来看一下:问题引入给定一个序列\(a\),给定\(Q\)个\(l,r\),求\(\sum_{i=l}^ra_i\)。这一类问题,我们明显可以暴力枚举,时间复杂度为......
  • 力扣 145. 二叉树的后序遍历 递归 迭代
    递归/** *Definitionforabinarytreenode. *publicclassTreeNode{ *  intval; *  TreeNodeleft; *  TreeNoderight; *  TreeNode(){} *  TreeNode(intval){this.val=val;} *  TreeNode(intval,TreeNodelef......
  • 力扣 144. 二叉树的前序遍历 递归 迭代
    递归/** *Definitionforabinarytreenode. *publicclassTreeNode{ *  intval; *  TreeNodeleft; *  TreeNoderight; *  TreeNode(){} *  TreeNode(intval){this.val=val;} *  TreeNode(intval,TreeNodelef......