PAT甲级1043.

目录

A1043

题目

样例

样例1

输入:

7
8 6 5 7 10 8 11

输出:

YES
5 7 6 8 11 10 8

样例2

输入:

7
8 10 11 8 6 7 5

输出:

YES
11 8 10 7 5 6 8

样例3

输入:

7
8 6 8 5 10 9 11

输出:

NO

思路和坑点

　　由于给的是前序序列，对于BST直接插入建树，同时建立对应的mirror树，然后保存两棵树其前序遍历的结果，如果和其中有一个与已给的序列相同，则认为YES，并后序输出对应的树，否则不是，输出NO。
　　使用全局变量tag控制插入的方式和遍历时候如何存放结果，tag=0，为一般树，tag=1为mirror树的操作。

AC代码

#include<bits/stdc++.h>
using namespace std;
int cnt=0;                            //后序输出时候空格控制的计数器 
typedef struct node{
    int data;
    struct node *left,*right;
}Node;
vector<int> pre,mpre;                //保存建立的一般树和镜像树的前序序列 
int tag=0;                            //tag全局变量用于控制对一般树或者镜像树的操作，tag=0，对应一般树，tag=1对应镜像树 
void preorder(Node *root){            //前序遍历 
    if(root==NULL) return;
    if(tag==0)
        pre.push_back(root->data);
    else
        mpre.push_back(root->data);
    preorder(root->left);
    preorder(root->right);
}
void postorder(Node *root){            //中序遍历 
    if(root==NULL) return;
    postorder(root->left);
    postorder(root->right);
    if(cnt) putchar(' ');
    printf("%d",root->data);
    cnt++;
}
void Insert(Node *&root,int x){        //插入建树 
    if(root==NULL){
        root=new Node;
        root->data=x;
        root->left=root->right=NULL;
        return;
    }
    if(x<root->data){
        if(tag==0) Insert(root->left,x);
        else    Insert(root->right,x);
    }
    else{
        if(tag==0) Insert(root->right,x);
        else    Insert(root->left,x);
    }
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    Node *root,*mroot;
    root=mroot=NULL;
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        tag=0;Insert(root,a[i]);
        tag=1;Insert(mroot,a[i]);
    } 
    tag=0;preorder(root);            //获取一般树的前序序列 
    tag=1;preorder(mroot);            //获取镜像树的前序序列 
    if(pre==a){                        //若有其中一个符合则按照求输出对应的后序序列 
        puts("YES");
        tag=0;
        postorder(root);
    }
    else if(mpre==a){
        puts("YES");
        tag=1;
        postorder(mroot);
    }
    else                            //如果都不是输出NO 
        puts("NO");
    return 0;
}