PAT A1043

迷南。 2022-03-07 03:46 197阅读 0赞

![clipboard.png][]  
简单的不用考虑平衡的二叉查询树；  
我发现我有读题障碍症。。。

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<vector>
    using namespace std;
    using std::vector;
    int n;
    struct node{
        int data;
        node* lchild;
        node* rchild;
    };
    vector<int>input;
    vector<int>inorder_;
    vector<int>change_inorder_;
    vector<int>postorder_;
    vector<int>change_postorder_;
    node* newNode(int x){
        node* root=new node;
        root->lchild=NULL;
        root->data=x;
        root->rchild=NULL;
        return root;
    }
    
    void insert(node* &root,int x){
        if(root==NULL){
            root=newNode(x);
            return ;
        }
        if(x<root->data){
            insert(root->lchild,x);
        }else{
            insert(root->rchild,x);
        }
        return ;
    }
    
    void inorder(node* root,vector<int>& vi){
        if(root==NULL)
            return;
        vi.push_back(root->data);
        inorder(root->lchild,vi);
        inorder(root->rchild,vi);
    }
    
    void postorder_change(node* root){
        if(root==NULL)
            return;
        postorder_change(root->lchild);
        postorder_change(root->rchild);
        swap(root->lchild,root->rchild);
    }
    
    void postorder(node* root,vector<int>& vi){
        if(root==NULL)
            return;
        postorder(root->lchild,vi);
        postorder(root->rchild,vi);
        vi.push_back(root->data);
    }
    
    int main(){
        int mem;
        node* root=NULL;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&mem);
            insert(root,mem);
            input.push_back(mem);
        }
        inorder(root,inorder_);
        postorder(root,postorder_);
        postorder_change(root);
        inorder(root,change_inorder_);
        postorder(root,change_postorder_);
        if(inorder_==input){
            printf("YES\n");
            for(int i=0;i<postorder_.size();i++){
                if(i==0){
                    printf("%d",postorder_[i]);
                }else{
                    printf(" %d",postorder_[i]);
                }
            }
        }else if(input==change_inorder_){
            printf("YES\n");
            for(int i=0;i<change_postorder_.size();i++){
                if(i==0){
                    printf("%d",change_postorder_[i]);
                }else{
                    printf(" %d",change_postorder_[i]);
                }
            }
        }else{
            printf("NO\n");
        }
        system("pause");
        return 0;
    }

[clipboard.png]: /images/20220307/c41ae2917f4643388bdeb9a63501e0cd.png