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
思路：我们只需要提炼题意几个关键词，首先是根据二叉搜索树的三个特点建树，
也顺便将其镜像树（原来放左边的放右边）写出来，
然后对比一下其前序遍历是不是对应给出的数列，是就输出其后序遍历的数列。
1 #include<bits/stdc++.h> 2 using namespace std; 3 //二叉搜索树特点：左节点比根节点小，右节点比根节点大 4 struct Node{ 5 int data; 6 struct Node *l; 7 struct Node *r; 8 }; 9 int s[1010],v[1010],tmp; 10 void create1(Node *root,int x){//建树 11 Node *p; 12 if(x<root->data){ 13 if(root->l==NULL){ 14 p=new Node; 15 p->data=x; 16 p->l=NULL; 17 p->r=NULL; 18 root->l=p; 19 return ; 20 } 21 else 22 create1(root->l,x); 23 } 24 else{ 25 if(root->r==NULL){ 26 p=new Node; 27 p->data=x; 28 p->l=NULL; 29 p->r=NULL; 30 root->r=p; 31 return ; 32 } 33 else 34 create1(root->r,x); 35 } 36 } 37 void create2(Node *root,int x){//镜像树 38 Node *p; 39 if(x>=root->data){ 40 if(root->l==NULL){ 41 p=new Node; 42 p->data=x; 43 p->l=NULL; 44 p->r=NULL; 45 root->l=p; 46 return ; 47 } 48 else 49 create2(root->l,x); 50 } 51 else{ 52 if(root->r==NULL){ 53 p=new Node; 54 p->data=x; 55 p->l=NULL; 56 p->r=NULL; 57 root->r=p; 58 return ; 59 } 60 else 61 create2(root->r,x); 62 } 63 } 64 void firstvisit(Node *p){//前序遍历：根左右 65 if(p!=NULL){ 66 v[tmp++]=p->data; 67 firstvisit(p->l); 68 firstvisit(p->r); 69 } 70 } 71 void lastvisit(Node *p){//后序遍历：左右根 72 if(p!=NULL){ 73 lastvisit(p->l); 74 lastvisit(p->r); 75 v[tmp++]=p->data; 76 } 77 } 78 int main(){ 79 int n,flag; 80 Node *root,*toor; 81 root=NULL; 82 scanf("%d",&n); 83 for(int i=0;i<n;i++){ 84 scanf("%d",&s[i]); 85 if(i==0)//根节点 86 { 87 root=new Node; 88 root->data=s[i]; 89 root->l=NULL; 90 root->r=NULL; 91 toor=new Node; 92 toor->data=s[i]; 93 toor->l=NULL; 94 toor->r=NULL; 95 } 96 else{ 97 create1(root,s[i]); 98 create2(toor,s[i]); 99 } 100 } 101 tmp=0; 102 flag=1; 103 firstvisit(root); 104 for(int i=0;i<n;i++){ 105 if(s[i]!=v[i]){ 106 flag=0; 107 break; 108 } 109 } 110 if(flag==1){ 111 printf("YES\n"); 112 tmp=0; 113 lastvisit(root); 114 printf("%d",v[0]); 115 for(int i=1;i<n;i++) 116 printf(" %d",v[i]); 117 118 } 119 else{ 120 tmp=0; 121 flag=1; 122 firstvisit(toor); 123 for(int i=0;i<n;i++){ 124 if(s[i]!=v[i]){ 125 flag=0; 126 break; 127 } 128 } 129 if(flag==1){ 130 printf("YES\n"); 131 tmp=0; 132 lastvisit(toor); 133 printf("%d",v[0]); 134 for(int i=1;i<n;i++) 135 printf(" %d",v[i]); 136 } 137 else 138 printf("NO\n"); 139 } 140 return 0; 141 }