PAT A1043

简单的不用考虑平衡的二叉查询树；我发现我有读题障碍症。。。
#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;
}