题干:

给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

解题报告:

   dfs求出这棵树来,然后bfs求层序遍历就行了。

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
struct Node {
	int val,l,r;
} node[MAX];
int tot;
int c[MAX],b[MAX]; 
int dfs(int len,int b[],int c[]) {//中序,后序 
	if(len <= 0) return -1;
	if(len == 1) {
		node[++tot].val = b[1];
		node[tot].l=node[tot].r = -1;
		return tot;
	}
	node[++tot].val = c[len];
	int res = tot;
	int l;
	for(l = 1; l<=len; l++) {
		if(b[l] == c[len]) break;
	}
	node[res].l = dfs(l-1,b,c);
	//node[res].r = dfs(len-l,b+l-1,c+l);
	node[res].r = dfs(len-l,b+l,c+l-1);
	return res;
} 
void bfs() {
	queue<int> q;
	q.push(1);
	while(q.size()) {
		int cur = q.front();q.pop();
		if(cur != 1) printf(" ");
		printf("%d",node[cur].val);
		if(node[cur].l != -1) q.push(node[cur].l);
		if(node[cur].r != -1) q.push(node[cur].r);
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i = 1; i<=n; i++) scanf("%d",c+i);
	for(int i = 1; i<=n; i++) scanf("%d",b+i);
	dfs(n,b,c);
	//printf("%d",node[1].val);
	bfs();
	return 0 ;
}