题目链接
题目大意
description
给出一个n个节点的树的后序遍历和中序遍历，求树的层序遍历。
思路
inspration
递归建一下树：维护序列的左端点和右端点，记录后序序列的下标用来表示节点的数据。然后直接层序遍历就好
坑点
pit
打完代码交了一发只得了五分，有点懵逼。自己造了几个样例也都没毛病，猜了一下估计是节点里的数据不一定比n小（比如有三个节点，节点的内容分别是2，3，4）。于是想试下猜想对不对，就搞了个稍微大一点的数组（也才3000），拿下标记录的节点数据，然后交了一发，结果直接过了。。有点侥幸吧。
代码
括号换行，又臭又长
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int in[32],post[32],n,now;
struct node
{
int no;
int lt;
int rt;
};
node num[3200];
int build(int left,int right)
{
if(left>right)
{
return -1;
}
now--;
int mid;
for(int i=0;i<n;i++)
if(in[i]==post[now])
{
mid=i;
break;
}
num[in[mid]].rt = build(mid+1,right);
num[in[mid]].lt = build(left,mid-1);
return in[mid];
}
int main()
{
for(int i=0;i<3200;i++)
num[i].no=i;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&post[i]);
}
for(int i=0;i<n;i++)
scanf("%d",&in[i]);
now=n;
build(0,n-1);
int flag=0;
queue<node>q;
q.push(num[post[n-1]]);
while(!q.empty())
{
node temp = q.front();
q.pop();
if(flag)
printf(" ");
else
flag=1;
printf("%d",temp.no);
if(temp.lt!=-1)
q.push(num[temp.lt]);
if(temp.rt!=-1)
q.push(num[temp.rt]);
}
printf("\n");
return 0;
}
