点击查看代码
//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";
}