1086 Tree Traversals Again (25 分)
#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node*l,*r;
};
int post[50],in[50],pre[50];
node* cratenode(int p1,int p2,int i1,int i2)
{
if(p1>p2)return NULL;
node* root=new node;
root->data=pre[p1];
int pos=find(in,in+i2,pre[p1])-in;
root->l=cratenode(p1+1,pos-i1+p1,i1,pos-1);
root->r=cratenode(pos-i1+p1+1,p2,pos+1,i2);
return root;
}
bool flag=false;
void postOrder(node *root)
{
if(root==NULL)return;
postOrder(root->l);
postOrder(root->r);
if(flag)cout<<" ";
else flag=true;
cout<<root->data;
}
int main()
{
int n;
cin>>n;
stack<int>st;
string s;
int data;
int i1=0,p1=0;
for(int i=0;i<2*n;i++)
{
cin>>s;
if(s=="Push"){
cin>>data;
st.push(data);
pre[p1++]=data;
}
else{
in[i1++]=st.top();
st.pop();
}
}
postOrder(cratenode(0,n-1,0,n-1));
return 0;
}
1020 Tree Traversals (25 分)
#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node*l,*r;
};
int in[50],post[50];
node* creatnode(int p1,int p2,int i1,int i2)
{
if(p1>p2)return NULL;
node* root=new node;
root->data=post[p2];
int pos=find(in,in+i2,post[p2])-in;
root->l=creatnode(p1,pos-1-i1+p1,i1,pos-1);
root->r=creatnode(pos-i1+p1,p2-1,pos+1,i2);
return root;
}
int main()
{
int i,j,k,n;
cin>>n;
for(i=0;i<n;i++)cin>>post[i];
for(i=0;i<n;i++)cin>>in[i];
node *root=creatnode(0,n-1,0,n-1);
node* Que[50];
int h=0,t=0;
Que[t++]=root;
while(h<t){
if(h!=0)cout<<" ";
node*p=Que[h++];
cout<<p->data;
if(p->l)Que[t++]=p->l;
if(p->r)Que[t++]=p->r;
}
return 0;
}
|
