程序设计天梯赛L2-11 (给定树的前序和中序，求层次遍历)

题目 题意: RT. 思路: 用指针写，C++的指针还比C语言好写一点。这个是通用写法，如果权值各不相同直接用map维护就好了。 时间复杂度: O(n) 代码:

#include
using namespace std;
int n,m,k,T;
const int N = 1e5+10;
struct node{
	int x;
	node*l;
	node*r;
};
node* newnode(int x)
{
	node *tmp = new node;
	tmp->x = x;
	tmp->l = NULL;
	tmp->r = NULL;
    return tmp;
}
int in[N];
int pre[N];
node* get(int l1,int r1,int l2,int r2)
{
	if(l1 > r1) return NULL;
	int idx;
	for(int i=l1;il = get(l1,idx-1,l2+1,l2+len);
	root->r = get(idx+1,r1,l2+len+1,r2);
	return root;
}
void bfs(node*root)
{
	queue q;
	q.push(root);
	// vector va;
    while(q.size())
    {
    	node*tmp = q.front(); q.pop();
    	if(tmp == root)
    	{
    		coutl);
    }
}
void solve()
{
	cin>>n;
	for(int i=1;i>in[i];
	for(int i=1;i>pre[i];
	node *root = get(1,n,1,n);
	bfs(root);
}
signed main(void)
{
	solve();
	return 0;
}