（25 分)

 

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

• 其左子树中所有结点的键值小于该结点的键值；
• 其右子树中所有结点的键值大于等于该结点的键值；
• 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

78 6 5 7 10 8 11

输出样例 1：

YES5 7 6 8 11 10 8

输入样例 2：

78 10 11 8 6 7 5

输出样例 2：

YES11 8 10 7 5 6 8

输入样例 3：

78 6 8 5 10 9 11

输出样例 3：

NO

 

因为前面写了二叉树的，所以这道题打算也用那种思路，写是写出来了，但是感觉怪怪的。

我建树是保存的下标编号，因为数可能是一样的，但是下标编号是唯一的。

建完树之后，写了个bfs搜了一下左右节点，发现好像也没毛病，但是自己想的一个样例过不了，肯定是错的代码，应该是后台样例比较水，所以满分水过了。。。

代码写的奇丑无比，但是还是希望有好心人能帮我想想我的代码哪里要改才能改对，过不了的样例：

2

2 1

输出应该为

YES

1 2

我的代码跑不出来。

后面看了一下别人的题解，发现还是别人的思路更简洁好实现一些，学到了，我这个弟弟。

 

先贴一下我的代码，不要学我的代码，有bug的，找不出来什么问题。。。

代码:

1 //L2-004 这是二叉搜索树吗？  2 #include
     
        3 using namespace std;  4 typedef long long ll;  5 const int maxn=1e5+10;  6 const int inf=0x3f3f3f3f;  7   8 int pre[maxn];  9 int n,flag=0; 10  11 struct node{ 12     int l,r; 13 }tree[maxn]; 14  15 int buildmin(int l,int r) 16 { 17     if(l>r) return 0; 18     if(r==-1) return 0; 19     int rt=pre[l]; 20     int p1=r; 21     while(pre[p1]>=rt){ 22         if(p1==l) break; 23         p1--; 24     } 25     int minn=inf,pos; 26     for(int i=p1;i>l;i--){ 27         if(minn>pre[i]){ 28             minn=pre[i]; 29             pos=i; 30         } 31     } 32     for(int i=pos;i>l;i--){ 33         if(pre[i]>=rt){ 34             flag=1;break; 35         } 36     } 37     if(flag==1){ 38         buildmin(0,-1); 39     } 40 //    cout<
      
       <
       
        r) return 0; 56     if(r==-1) return 0; 57     int rt=pre[l]; 58     int p1=r; 59     while(pre[p1]
        
         l;i--){ 63         if(pre[i]
         

vec; 86 queue

que; 87 que.push(x); 88 while(!que.empty()){ 89 int ret=que.front(); 90 que.pop(); 91 if(ret==0) break; 92 vec.push_back(ret); 93 if(tree[ret].l!=0){ 94 que.push(tree[ret].l); 95 } 96 if(tree[ret].r!=0){ 97 que.push(tree[ret].r); 98 } 99 }100 int l=vec.size();101 for(int i=0;i