题目:http://pat.zju.edu.cn/contests/pat-a-practise/1043
题解:
1:通过输入构造二叉排序树
2:先序遍历并与输入顺序比较
3:如果比较不符合再构造镜像二叉排序树
4:比较输出结果
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff #define MAX 1005 struct point { int value; int left; int right; } node[MAX]; int a[MAX],b[MAX]; int deep; void dfs(int x,int idx) {//构造二叉树 if(node[x].value>node[idx].value) { //应在当前结点左子树 if(node[x].left==-1) node[x].left=idx; else dfs(node[x].left,idx); } else { //应在当前结点右子树 if(node[x].right==-1) node[x].right=idx; else dfs(node[x].right,idx); } } void dfsP(int x,int idx) {//构造镜像排序二叉树 if(node[x].value>node[idx].value) { //应在当前结点右子树 if(node[x].right==-1) node[x].right=idx; else dfsP(node[x].right,idx); } else { //应在当前结点左子树 if(node[x].left==-1) node[x].left=idx; else dfsP(node[x].left,idx); } } void dfsPre(int x) {//先序遍历 b[deep]=node[x].value; ++deep; if(node[x].left!=-1) dfsPre(node[x].left); if(node[x].right!=-1) dfsPre(node[x].right); } void dfsPost(int x) {//后序遍历 if(node[x].left!=-1) dfsPost(node[x].left); if(node[x].right!=-1) dfsPost(node[x].right); b[deep]=node[x].value; ++deep; } int main() { int n; scanf("%d",&n); for(int i=0; i<n; ++i) { scanf("%d",&node[i].value); a[i]=node[i].value; node[i].left=node[i].right=-1; } for(int i=1; i<n; ++i) {//构造排序二叉树 dfs(0,i); } deep=0; dfsPre(0);//先序遍历 bool flag=true; for(int i=0; i<n; ++i) {//比较 if(a[i]!=b[i]) { flag=false; break; } } if(flag)//先序遍历与输入相同 { printf("YES\n"); deep=0; dfsPost(0);//后序遍历 bool first=true; for(int i=0; i<n; ++i) { if(first) { printf("%d",b[i]); first=false; } else printf(" %d",b[i]); } printf("\n"); } else { for(int i=0; i<n; ++i) node[i].left=node[i].right=-1; for(int i=1; i<n; ++i) {//构造镜像二叉排序树 dfsP(0,i); } deep=0; dfsPre(0); flag=true; for(int i=0; i<n; ++i) {//比较 if(a[i]!=b[i]) { flag=false; break; } } if(flag)//镜像二叉排序树的先序遍历与输入相同 { printf("YES\n"); deep=0; dfsPost(0); bool first=true; for(int i=0; i<n; ++i) { if(first) { printf("%d",b[i]); first=false; } else printf(" %d",b[i]); } printf("\n"); } else printf("NO\n"); } return 0; }