#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct node{
int v, h;
node* L;
node* R;
};
vector<int> result[35];
vector<int> in, post;
node* create(int inL, int inR, int postL, int postR){
if(postL > postR){
return NULL;
}
node* root = new node;
root->v = post[postR];
int k;
for(k = inL; k <= inR; k++){
if(in[k] == post[postR]){
break;
}
}
int numLeft = k - inL;
root->L = create(inL, k - 1, postL, postL + numLeft - 1);
root->R = create(k + 1, inR, postL+numLeft, postR - 1);
return root;
}
void bfs(node* root){
queue<node*> q;
root->h = 0;
q.push(root);
while(!q.empty()){
node* now = q.front();
q.pop();
result[now->h].push_back(now->v);
if(now->L != NULL){
now->L->h = now->h + 1;
q.push(now->L);
}
if(now->R != NULL){
now->R->h = now->h + 1;
q.push(now->R);
}
}
}
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
int a;
scanf("%d", &a);
in.push_back(a);
}
for(int i = 0; i < n; i++){
int a;
scanf("%d", &a);
post.push_back(a);
}
node* root = create(0, n-1, 0, n-1);
bfs(root);
printf("%d", result[0][0]);
for(int i = 1; i < 35; i++){
if(i % 2 == 1){
for(int j = 0; j < result[i].size(); j++){
printf(" %d", result[i][j]);
}
}else{
for(int j = result[i].size() - 1; j >= 0; j--){
printf(" %d", result[i][j]);
}
}
}
return 0;
}
A1127 ZigZagging on a Tree (30分)
原文:https://www.cnblogs.com/tsruixi/p/13068663.html