玩转二叉树

玩转二叉树

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

输入格式：
输入第一行给出一个正整数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

两种方法：
（1）先还原出镜像二叉树，即在原有方式的基础上让root->left=原来root->right的值，root->right=原来root->left的值，还原后照常BFS即可
（2）正常还原出镜像二叉树，但是BFS时先让右子树入队，再让左子树入队即可。
这里给出第二种方法：

//#define LOCAL
#include<iostream>
#include<queue>
using namespace std;
struct node {
	int data;
	node* left;
	node* right;
};
int pre[33],in[33];
node* create(int prel,int prer,int inl,int inr) {
	if(inl>inr) {
		return NULL;
	}
	int k;
	for(k=inl; k<=inr; k++) {
		if(in[k]==pre[prel]) {
			break;
		}
	}
	int numl=k-inl;
	node* root=new node;
	root->data=pre[prel];
	root->left=create(prel+1,prel+numl,inl,k-1);
	root->right=create(prel+numl+1,prer,k+1,inr);
	return root;
}
void mirrorBFS(node* root) {
	if(!root)return;
	queue<node*> q;
	q.push(root);
	bool isback=false;
	while(!q.empty()){
		node* t=q.front();
		q.pop();
		if(isback)fputc(' ',stdout);
		else isback=true;
		cout<<t->data;
		if(t->right)q.push(t->right);
		if(t->left)q.push(t->left);
	}
}
int main(void) {
#ifdef LOCAL
	freopen("7-2 玩转二叉树.txt","r",stdin);
#endif
	int n;
	while(cin>>n) {
		for(int i=0; i<n; i++) {
			cin>>in[i];
		}
		for(int i=0; i<n; i++) {
			cin>>pre[i];
		}
		node* root=create(0,n-1,0,n-1);
		mirrorBFS(root);
	}
}