7-11 玩转二叉树 （25 分)
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
输出样例：
4 6 1 7 5 3 2

呃，想清楚就好了

#include<bits/stdc++.h>

using namespace std;

const int maxn = 31;

class T
{
public:
	int num;
	T* lc, * rc;
	T()
	{
		num = 0;
		lc = rc = NULL;
	}
};

int n;

int zhong[maxn], qian[maxn];

T* root;

queue<T*> q[2];
int pre = 0, nextt = 1;

void build(T &s, int zs, int ze, int qs, int qe)
{
	set<int> se;
	int r = qian[qs];
	s.num = r;
	if (zs == ze)return;
	int lzs, lze, rzs, rze;
	int lqs, lqe, rqs, rqe;
	int zmid = zs;
	while (zhong[zmid] != r)
	{
		se.insert(zhong[zmid]);
		zmid++;
	}
	lzs = zs; lze = zmid - 1;
	rzs = zmid + 1; rze = ze;
	int qmid = qs + 1;
	bool flag = (se.find(qian[qmid]) != se.end());
	if (flag)
	{
		while ((se.find(qian[qmid]) != se.end()) == flag && qmid <= qe)qmid++;
		lqs = qs + 1; lqe = qmid - 1;
		rqs = qmid; rqe = qe;
	}
	else
	{
		lqs = qs + 1; lqe = qs;
		rqs = qs + 1; rqe = qe;
	}
	
	if (lze >= lzs && lqe >= lqs)
	{
		s.lc = new T();
		build(*s.lc, lzs, lze, lqs, lqe);
	}
	
	if (rze >= rzs && rqe >= rqs)
	{
		s.rc = new T();
		build(*s.rc, rzs, rze, rqs, rqe);
	}
}


void out()
{
	q[0].push(root);
	while (q[0].size() || q[1].size())
	{
		while (q[pre].size())
		{
			T* p = q[pre].front();
			q[pre].pop();
			if (p != root)printf(" ");
			printf("%d", p->num);
			if (p->rc != NULL)
			{
				q[nextt].push(p->rc);
			}
			if (p->lc != NULL)
			{
				q[nextt].push(p->lc);
			}
		}
		swap(pre, nextt);
	}
	printf("\n");
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i != n; i++)
	{
		scanf("%d", &zhong[i]);
	}
	for (int i = 0; i != n; i++)
	{
		scanf("%d", &qian[i]);
	}
	root = new T();
	build(*root, 0, n - 1, 0, n - 1);

	out();

	return 0;
}