天梯程序设计竞赛 L2-004. 这是二叉搜索树吗？

L2-004. 这是二叉搜索树吗？

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

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

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

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

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

输入格式：

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

输出格式：

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

输入样例1：

7
8 6 5 7 10 8 11

输出样例1：

YES
5 7 6 8 11 10 8

输入样例2：

7
8 10 11 8 6 7 5

输出样例2：

YES
11 8 10 7 5 6 8

输入样例3：

7
8 6 8 5 10 9 11

输出样例3：

NO

根据输入序列先建树，然后判断建的树的前序遍历结果和输入序列是否相同，如果相同则输出YES，并输出后序遍历结果，否则输出NO.

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<set>
  4 
  5 using namespace std;
  6 
  7 int num[1005],n,qian[1005],pos=1;
  8 struct node
  9 {
 10     int data;
 11     node* lchild;
 12     node* rchild;
 13 };
 14 void build(int flag,node * t,int x)
 15 {
 16     node *p=t,*f = t;
 17     if(flag)
 18     {
 19         while(p)
 20         {
 21             f = p;
 22             if(x>=p->data)
 23                 p = p->lchild;
 24             else
 25                 p = p->rchild;
 26         }
 27         p = new node;
 28         p->data = x;
 29         p->lchild = p->rchild = NULL;
 30         if(x<f->data)
 31             f->rchild = p;
 32         else
 33             f->lchild = p;
 34     }
 35     else
 36     {
 37         while(p)
 38         {
 39             f = p;
 40             if(x<p->data)
 41                 p = p->lchild;
 42             else
 43                 p = p->rchild;
 44         }
 45         p = new node;
 46         p->data = x;
 47         p->lchild = p->rchild = NULL;
 48         if(x>=f->data)
 49             f->rchild = p;
 50         else
 51             f->lchild = p;
 52 
 53     }
 54 }
 55 void ss(node *t)
 56 {
 57     if(t)
 58     {
 59         qian[pos++]=t->data;    //避免参数在递归中出错，定义pos为全局变量
 60         ss(t->lchild);
 61         ss(t->rchild);
 62     }
 63 }
 64 void hou(node *t,node * pan)
 65 {
 66     if(t)
 67     {
 68         hou(t->lchild,pan);
 69         hou(t->rchild,pan);
 70         if(t!=pan)
 71             cout<<t->data<<' ';
 72     }
 73 }
 74 int main()
 75 {
 76     cin>>n;
 77     for(int i = 1; i <= n; i++)
 78         cin>>num[i];
 79     if(n==1)        //如果n==1，则不用判断直接输出
 80         cout<<"YES"<<endl<<num[1]<<endl;
 81     else
 82     {
 83         int flag=0;     //用来标记序列是否为镜像，在建树时作为参数传递
 84         if(num[2]>=num[1])
 85             flag=1;
 86         node root;
 87         root.data=num[1];
 88         root.lchild = root.rchild = NULL;
 89         for(int i = 2; i <= n; i++)
 90             build(flag,&root,num[i]);
 91         ss(&root);      //前序遍历
 92         int j;
 93         for(j = 1; j <= n; j++)
 94             if(num[j]!=qian[j])
 95                 break;
 96         if(j<=n)
 97             cout<<"NO"<<endl;
 98         else
 99         {
100             cout<<"YES"<<endl;
101             hou(&root,&root);   //之所以穿两个参数，是为了控制格式输出，一行的首尾不得有多余空格
102             cout<<num[1]<<endl;
103         }
104     }
105     return 0;
106 }