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
#include <iostream> #include<cstring> #include<cstdio> using namespace std; struct node { int num,left,right; }tree[1005]; int i,j,n; int a[1005],b[1005],l; void buildtree(int k) { if (k>n) return; tree[++l].num=a[k]; tree[l].left=-1; tree[l].right=-1; int i=1; while(1) { while(a[k]<tree[i].num && tree[i].left!=-1) i=tree[i].left; if (tree[i].left==-1 && a[k]<tree[i].num) { tree[i].left=l; break; } while(a[k]>=tree[i].num && tree[i].right!=-1) i=tree[i].right; if (tree[i].right==-1 && a[k]>=tree[i].num) { tree[i].right=l; break; } } buildtree(k+1); return ; } void work1(int k) { b[++l]=tree[k].num; if (tree[k].left!=-1) work1(tree[k].left); if (tree[k].right!=-1) work1(tree[k].right); return; } void work2(int k) { b[++l]=tree[k].num; if (tree[k].right!=-1) work2(tree[k].right); if (tree[k].left!=-1) work2(tree[k].left); return; } void cal1(int k) { if (tree[k].left!=-1) cal1(tree[k].left); if (tree[k].right!=-1) cal1(tree[k].right); b[++l]=tree[k].num; return; } void cal2(int k) { if (tree[k].right!=-1) cal2(tree[k].right); if (tree[k].left!=-1) cal2(tree[k].left); b[++l]=tree[k].num; return; } int main() { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); tree[1].num=a[1]; tree[1].left=-1; tree[1].right=-1; l=1; buildtree(2); //for(i=1;i<=n;i++) // printf("%d:%d %d\n",tree[i].num,tree[tree[i].left].num,tree[tree[i].right].num); l=0; memset(b,0,sizeof(b)); work1(1); for(i=1;i<=n;i++) if (a[i]!=b[i]) break; if(i>n) { printf("YES\n"); memset(b,0,sizeof(b)); l=0; cal1(1); for(i=1;i<n;i++) printf("%d ",b[i]); printf("%d\n",b[n]); } else { l=0; memset(b,0,sizeof(b)); work2(1); for(i=1;i<=n;i++) if (a[i]!=b[i]) break; if (i>n) { printf("YES\n"); memset(b,0,sizeof(b)); l=0; cal2(1); for(i=1;i<n;i++) printf("%d ",b[i]); printf("%d\n",b[n]); } else printf("NO\n"); } return 0; }