程序设计天梯赛 L2-002 (由后序和前序建树)

题目 题意: 给定一颗树的后序遍历和中序遍历，求层次遍历。 思路: 不会高端做法，先建树吧，递归建树。然后bfs一下就行。 get(int l1,int r1,int l2,int r2) //表示后序和中序分别对应的区间 树根是b[r1]，在中序中找到他为idx，他的左右两侧分别是左子树和右子树。 而对于后序来说，区间不太好找。首先根据中序计算左子树大小，len = idx-l2，那么后序左子树起点l1和长度确定了，[l1,l1+len-1]，右子树则是[l1+len,r1-1]. 时间复杂度: O(n) 代码:

#include
using namespace std;
#define mem(a,x) memset(a,x,sizeof(a))
typedef pair PII; 
const int N = 102;
int n,m,k,T;
map sonl;
map sonr;
int a[N]; //中序
int b[N]; //后序
int in[N];
int get(int l1,int r1,int l2,int r2) //后序和中序 
{
	if(l1>r1 || l2>r2) return -1;
	if(l1==r1) {in[b[l1]]++;return b[l1];}
	if(l2==r2) {in[a[l2]]++;return a[l2];}
	int root = b[r1];
	int idx = 1; 
    for(int i=l2;i