给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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
勉强敲出来了，包括已知中序和前序建树求层序遍历树的序列，虽然还有两组数据没有过，但是也够了。
O(∩_∩)O哈哈~
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
#include <cstdlib> using namespace std;
const int maxn = ;
int n, num;
string a, b;
typedef struct node{
int data ;
struct node *lchild, *rchild;
}*BiTree, BiNode; void Creat_Tree(BiTree & T, string a, string b){
if( b.length() == ){
T = NULL ;
return ;
}
char root_Node = b[];
int index = a.find(b[]);
string l_a = a.substr(,index);
string r_a = a.substr(index+);
int l_len = l_a.length();
int r_len = r_a.length();
string l_b = b.substr(,l_len);
string r_b = b.substr(+l_len); T = (BiTree)malloc(sizeof(BiNode));
if( T!=NULL){
T -> data = root_Node - ;
Creat_Tree(T->lchild, l_a, l_b);
Creat_Tree(T->rchild, r_a, r_b);
}
} int main(){
BiTree T;
cin >> n ;
if( n == ) return ;
for(int i=; i<n; i++){
cin >> num ;
a.push_back(num + '');
}
for(int i=; i<n; i++){
cin >> num ;
b.push_back(num+'');
} Creat_Tree(T,a,b);
queue<BiTree> q;
q.push(T);
bool flag = true ;
while( !q.empty() ){
BiTree m = q.front();
if( flag ){
cout << m->data ;
flag = false ;
}
else{
cout << " " << m->data ;
}
if( m->rchild ) q.push(m->rchild);
if( m->lchild ) q.push(m->lchild);
q.pop();
}
cout << endl ; return ;
}
加个正确的解答吧。完美AC的。
来源：http://blog.csdn.net/idealism_xxm/article/details/51584798
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int MAXN=; int n,cnt,root;
int inod[MAXN],preod[MAXN];
int q[],head,tail; struct Node {
int lson,rson,num;
}tr[MAXN]; int dfs(int pl,int pr,int il,int ir) {
if(pl==pr) {
tr[cnt].lson=tr[cnt].rson=-;
tr[cnt].num=preod[pl];
return cnt++;
}
for(int i=il;i<=ir;++i) {
if(preod[pl]==inod[i]) {
int cur=cnt++;
tr[cur].lson=tr[cur].rson=-;
tr[cur].num=preod[pl];
if(il<i) {
tr[cur].lson=dfs(pl+,pl+i-il,il,i-);
}
if(i<ir) {
tr[cur].rson=dfs(pl+i-il+,pr,i+,ir);
}
return cur;
}
}
return cnt;
} int main() {
while(==scanf("%d",&n)) {
for(int i=;i<n;++i) {
scanf("%d",inod+i);
}
for(int i=;i<n;++i) {
scanf("%d",preod+i);
}
cnt=;
root=dfs(,n-,,n-);
head=tail=;
if(tr[root].rson!=-) {
q[tail++]=tr[root].rson;
}
if(tr[root].lson!=-) {
q[tail++]=tr[root].lson;
}
printf("%d",tr[root].num);
while(head!=tail) {
printf(" %d",tr[q[head]].num);
if(tr[q[head]].rson!=-) {
q[tail++]=tr[q[head]].rson;
}
if(tr[q[head]].lson!=-) {
q[tail++]=tr[q[head]].lson;
}
++head;
}
printf("\n");
}
return ;
}