搜索树判断

5-10 搜索树判断   (25分)

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数N（/le≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式:

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例1:

78 6 5 7 10 8 11
输出样例1:
YES5 7 6 8 11 10 8
输入样例2:
78 6 8 5 10 9 11
输出样例2:
NO
嗯，先序遍历，就是插入的顺序。我们可以按照先序插入建树，看一下是不是和序列一样。
因为可以翻转，所以建两棵反向的树。如果其中一棵树满足就直接输出后序遍历。
#include <bits/stdc++.h>using namespace std;const int MAXN=1005;const int inf=1e9;int n,m,k,pos,s;int num[MAXN];int ans1[MAXN],ans2[MAXN];struct node{    int key;    struct node*l,*r;    node()    {        l=r=NULL;    }};void build_tree1(struct node*&root,int x){    if(!root)    {        root=new node();        root->key=x;        return ;    }    if(x<root->key)build_tree1(root->l,x);    else build_tree1(root->r,x);}void build_tree2(struct node*&root,int x){    if(!root)    {        root=new node();        root->key=x;        return ;    }    if(x<root->key)build_tree2(root->r,x);    else build_tree2(root->l,x);}int cnt=0;void get_in(struct node*root,int *ans){    if(!root)return;    ans[cnt++]=root->key;    if(root->l)get_in(root->l,ans);    if(root->r)get_in(root->r,ans);}void get_out(struct node*root,int *ans){    if(!root)return;    if(root->l)get_out(root->l,ans);    if(root->r)get_out(root->r,ans);    ans[cnt++]=root->key;}bool check(int *ans){    for(int i=0;i<n;++i)if(num[i]!=ans[i])return 0;    return 1;}int main(){    scanf("%d",&n);    struct node*root1=NULL,*root2=NULL;    for(int i=0;i<n;++i)    {        scanf("%d",&num[i]);        build_tree1(root1,num[i]);        build_tree2(root2,num[i]);    }    cnt=0;    get_in(root1,ans1);    cnt=0;    get_in(root2,ans2);    if(check(ans1))    {        puts("YES");        cnt=0;        get_out(root1,ans1);        for(int i=0;i<n-1;++i)PRintf("%d ",ans1[i]);        printf("%d/n",ans1[n-1]);    }    else        if(check(ans2))    {        puts("YES");        cnt=0;        get_out(root2,ans2);        for(int i=0;i<n-1;++i)printf("%d ",ans2[i]);        printf("%d/n",ans2[n-1]);    }    else puts("NO");    return 0;}