- 首页 > it技术 > >
1127|1127 ZigZagging on a Tree（30 分）
#include
#include
#include
#include
using namespace std;
const int maxn = 50;
struct node {
int data, layer;
node *lchild, *rchild;
};
int n;
int in[maxn], post[maxn];
vectorans[maxn];
node* creat(int postL,int postR,int inL,int inR)
{
if (postL > postR)return NULL;
node* root = new node;
root->data = https://www.it610.com/article/post[postR];
int k;
for (k = inL;
k <= inR;
k++)
{
if (in[k] == root->data)break;
}
int leftnum = k - inL;
root->lchild = creat(postL, postL + leftnum - 1, inL, k - 1);
root->rchild = creat(postL + leftnum, postR-1, k + 1, inR);
return root;
}
int maxlayer = 0;
void layerorder(node*root)
{
root->layer = 0;
queueq;
q.push(root);
while (!q.empty())
{
node* front = q.front();
q.pop();
ans[front->layer].push_back(front->data);
maxlayer = max(maxlayer, front->layer);
if (front->lchild)front->lchild->layer = front->layer + 1, q.push(front->lchild);
if (front->rchild)front->rchild->layer = front->layer + 1, q.push(front->rchild);
}
}
int main()
{
scanf("%d", &n);
for (int i = 0;
i < n;
i++)scanf("%d", &in[i]);
for (int i = 0;
i < n;
i++)scanf("%d", &post[i]);
node* root = creat(0, n - 1, 0, n - 1);
layerorder(root);
int cnt = 0;
for (int i = 0;
i <= maxlayer;
i++)
{
if (i % 2 == 0)reverse(ans[i].begin(), ans[i].end());
for (auto it = ans[i].begin();
it != ans[i].end();
it++)
{
printf("%d", *it);
cnt++;
if (cnt != n)printf(" ");
}
}
return 0;
}
推荐阅读
