【问题描述】试写一个判别给定二叉树是否为二叉排序树的算法。以前序遍历序列和中序遍历序列给出该二叉树的结点，并创建该二叉树。然后再进行判断。请注意，树中结点关键字可能相同。 先创建二叉树的链式存储，再对其进行判断。 【样例输入】 6 4 5 8 6 9 0 4 5 6 6 8 9 0 【样例输出】 true C/C++源代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10010;
int pre[maxn],in[maxn],n;
bool flag=false;//判断是否为二叉排序树的标志
struct node{
    int data;
    node* lchild,*rchild;
};
node* build(int preL,int preR,int inL,int inR){
    if(preL>preR) return NULL;
    node* root=new node;
    root->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==pre[preL]) break;
    }
    int numleft=k-inL;
    root->lchild=build(preL+1,preL+numleft,inL,k-1);
    root->rchild=build(preL+numleft+1,preR,k+1,inR);
    return root;
}
void traversal(node* root){
    if(root==NULL) return;
    traversal(root->lchild);
    if(flag==true) return;//已经不是二叉排序树了，就可以直接返回了
    if(root->lchild!=NULL&&root->rchild!=NULL){
        if(root->lchild->data>root->data||root->rchild->data<root->data){
            flag=true;
            return;
        }
    }
    traversal(root->rchild);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>pre[i];
    for(int i=0;i<n;i++)
        cin>>in[i];
    node* root=build(0,n-1,0,n-1);
    traversal(root);
    if(flag==true) cout<<"false"<<endl;
    else cout<<"true"<<endl;
    return 0;
}