PAT A 1043 Is It a Binary Search Tree

A Binary Search Tree (BST) is recursively defined as a binary tree which has the fol‐lowing properties:
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.
If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.
Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.
Input Specification:
Each input file contains one test case. For each case, the first line contains a posi‐tive integer (). Then integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1:

7
8 6 5 7 10 8 11

Sample Output 1:

YES
5 7 6 8 11 10 8

Sample Input 2:

7
8 10 11 8 6 7 5

Sample Output 2:

YES
11 8 10 7 5 6 8

Sample Input 3:

7 8 6 8 5 10 9 11

Sample Output 3:

NO

题目大意：
给出一个序列 用这个序列生成bst二叉排序树
然后这个二叉排序树 对应 一个镜像树 大概就是 大的在左子树 小的在右子树
如果这个二叉排序树的前序序列和初始给出的序列相同 输出这个二叉排序树的后序序列
如果这个二叉排序树的镜像树的前序序列和初始给出的序列相同 输出这个镜像树的后序序列
然后其实 这个镜像树的前序序列 就是二叉排序树的 ：根右左
这个镜像树的后序序列 就是二叉排序树的：右左根
都不是 puts(“NO”);

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int n;
const int N = 1010;
struct Node
{
    int data;
    Node* lchild;
    Node* rchild;
};
vector<int> start;
vector<int> post,post1;
vector<int> pre,pre1;

void insert(Node* &root,int x)
{
    if(root == NULL)
    {
        root = new Node;
        root->data = x;
        root->lchild = NULL;
        root->rchild = NULL;
    }
    else{
        if(x < root->data) insert(root->lchild,x);
        else insert(root->rchild,x);
    }
}


void preorder(Node* root)
{
    if(root == NULL) return;
    
    pre.push_back(root->data);
    
    preorder(root->lchild);
    
    preorder(root->rchild);
}

void preorder1(Node* root)
{
    if(root == NULL) return;
    
    pre1.push_back(root->data);
    
    preorder1(root->rchild);
    
    preorder1(root->lchild);
}

void postorder(Node* root)
{
    if(root == NULL) return;
    
    postorder(root->rchild);
    
    postorder(root->lchild);

    post.push_back(root->data);
}

void postorder1(Node* root)
{
    if(root == NULL) return;
    
    postorder1(root->lchild);
    
    postorder1(root->rchild);

    post1.push_back(root->data);
}

int main()
{
    cin>>n;
    Node* root = NULL;

    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        start.push_back(x);
        insert(root,x);
    }
    
    preorder(root);//根左右
    preorder1(root);//根右左
    
    bool flag = true;
    for(int i=0;i<n;i++)
    {
        if(start[i] != pre[i])
        {
            flag = false;
            break;
        }
    }
    
    bool flag1 = true;
    for(int i=0;i<n;i++)
    {
        if(start[i] != pre1[i])
        {
            flag1 = false;
        }
    }
    
    if(!flag && !flag1) puts("NO");
    else if(flag1)
    {
        puts("YES");
        postorder(root);//右左根
        for(int i=0;i<n;i++) 
        {
            if(i<n-1) cout<<post[i]<<' ';
            else cout<<post[i]<<endl;
        }
    }
    else if(flag)
    {
        puts("YES");
        postorder1(root);//左右根
        for(int i=0;i<n;i++) 
        {
            if(i<n-1) cout<<post1[i]<<' ';
            else cout<<post1[i]<<endl;
        }
    }
    
    return 0;
}

放在结尾：
推荐大家一首很好听的歌：网易云《好想我回来啊》