【模板】判断二叉查找树

二叉查找树其实！

就是平衡树啦

noip 2013 PJ T28 完善程序：

（二叉查找树） 二叉查找树具有如下性质： 每个节点的值都大于其左子树上所有节点的 值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数 n，表示这棵树有 n 个顶点， 编号分别为 1, 2, ⋯ , n，其 中编号为 1 的为根结点。之后的第 i 行有三个数 value, left_child , right_child ，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用 0 代替。输出 1 表示这棵树是二叉查找树，输出0 则表示不是。

const int N=1e6+10;

int n,m;

struct node{
	int val,lson,rson;
}a[N];

inline bool is_bst(int root,int l_bound,int u_bound){
    if(root==0)return 1;
    int cur=a[root].val;
    return (l_bound <cur) && (cur < u_bound) && is_bst(a[root].lson,l_bound,cur) && is_bst(a[root].rson,cur,u_bound);
	//值域严格小于/大于 
}

int main(){
    rd(n);
    rep(i,1,n){
        rd(a[i].val),rd(a[i].lson),rd(a[i].rson);
    }
    cout<<is_bst(1,INT_MIN,INT_MAX);
    return 0;
}
//严格小于/大于 
/*
5
6 4 5
5 0 0
3 0 0
4 3 2
7 0 0
*/
//1
//可以等于
/*
5
6 4 5
5 0 0
3 0 0
5 3 2
7 0 0
*/
//1