遍历二叉搜索树习题
PAT A1043

输入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 <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>



using namespace std;



struct node{

    int data;
    node* left,*right;

};




void insert(node* &root,int data)
{
    if(root==NULL)
    {
        root=new node;
        root->data=data;
        root->left=root->right=NULL;
        return;

    }

    if(data < root->data)
    {
        insert(root->left,data);

    }
    else
    {
        insert(root->right,data);

    }


}



void preorder(node* root,vector<int>&vi)
{
    if(root == NULL)
    {
        return;
    }

    vi.push_back(root->data);
    preorder(root->left,vi);
    preorder(root->right,vi);



}

void preorder_mirror(node* root,vector<int>&vi)
{
    if(root==NULL)
    {
        return;

    }

    vi.push_back(root->data);

    preorder_mirror(root->right,vi);
    preorder_mirror(root->left,vi);




}

void postorder(node* root,vector<int>&vi)
{
    if(root==NULL)
    {
        return;

    }

    postorder(root->left,vi);
    postorder(root->right,vi);

    vi.push_back(root->data);



}



void postorder_mirror(node* root,vector<int>& vi)
{
    if(root==NULL)
    {

        return;
    }


    postorder_mirror(root->right,vi);
    postorder_mirror(root->left,vi);

    vi.push_back(root->data);




}




//origin 存放初始序列
//pre、post为先序、后序，pre_m、post_m为镜像树先序、后序

vector<int> origin,pre,pre_m,post,post_m;




int main()
{
    int n,data;

    node* root=NULL;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&data);

        origin.push_back(data);
        insert(root,data);

    }

    preorder(root,pre);
    preorder_mirror(root,pre_m);
    postorder(root,post);
    postorder_mirror(root,post_m);


    if(origin==pre)
    {
        printf("YES\n");

        for(auto x:post)
        {
            printf("%d ",x);
        }


    }
    else if(origin == pre_m)
    {
        printf("YES\n");

        for(auto x:post_m)
        {
            printf("%d ",x);
        }


    }
    else
    {


        printf("NO\n");

    }


    return 0;

}