pta7-15 树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列

#include <bits/stdc++.h>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef struct Node
{
	int val;
	struct Node *l,*r;
}node,*tree;

void create(int *in,int *post,int len,tree &T)
{
	if(!len)
	{
		T=nullptr;
		return ;
	}
	T=new node({post[len-1],nullptr,nullptr});
	int i=0;
	//for(int i=0;in[i]!=post[len-1];i++);
	while(in[i]!=post[len-1]) i++;
	create(in,post,i,T->l);
	create(in+1+i,post+i,len-i-1,T->r);
}
void level(tree T)
{
	queue<tree> q;
	tree p;
	bool flag=false;
	if(T)
	{
		q.push(T);
		while(!q.empty())
		{
			p=q.front();
			
			if(flag) cout<<" "<<p->val;
			else
			{
				cout<<p->val;
				flag=true;
			}
			q.pop();//
			if(p->l) q.push(p->l);
			if(p->r) q.push(p->r);
		}
		puts("");
	}
}
int main()
{
//	freopen("D:\\LYJ.txt","r",stdin);
	int in[35],post[35],n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>post[i];
	for(int i=0;i<n;i++) cin>>in[i];
	tree T=nullptr;
	create(in,post,n,T);
	level(T);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63