ACM题⽬————玩转⼆叉树
给定⼀棵⼆叉树的中序遍历和前序遍历，请你先将树做个镜⾯反转，再输出反转后的层序遍历的序列。所谓镜⾯反转，是指将所有⾮叶结点的左右孩⼦对换。这⾥假设键值都是互不相等的正整数。
输⼊格式：
输⼊第⼀⾏给出⼀个正整数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 = 35 ;
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() == 0 ){
T = NULL ;
return ;
}
cstring转为intchar root_Node = b[0];
int index = a.find(b[0]);
string l_a = a.substr(0,index);
string r_a = a.substr(index+1);
int l_len = l_a.length();
int r_len = r_a.length();
string l_b = b.substr(1,l_len);
string r_b = b.substr(1+l_len);
T = (BiTree)malloc(sizeof(BiNode));
if( T!=NULL){
T -> data = root_Node - 48 ;
Creat_Tree(T->lchild, l_a, l_b);
Creat_Tree(T->rchild, r_a, r_b);
}
}
int main(){
BiTree T;
cin >> n ;
if( n == 0 ) return0 ;
for(int i=0; i<n; i++){
cin >> num ;
a.push_back(num + '0');
}
for(int i=0; i<n; i++){
cin >> num ;
b.push_back(num+'0');
}
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 ;
return0;
}
加个正确的解答吧。完美AC的。
来源：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=35;
int n,cnt,root;
int inod[MAXN],preod[MAXN];
int q[35],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=-1;
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=-1;
tr[cur].num=preod[pl];
if(il<i) {
tr[cur].lson=dfs(pl+1,pl+i-il,il,i-1);            }
if(i<ir) {
tr[cur].rson=dfs(pl+i-il+1,pr,i+1,ir);            }
return cur;
}
}
return cnt;
}
int main() {
while(1==scanf("%d",&n)) {
for(int i=0;i<n;++i) {
scanf("%d",inod+i);
}
for(int i=0;i<n;++i) {
scanf("%d",preod+i);
}
cnt=0;
root=dfs(0,n-1,0,n-1);
head=tail=0;
if(tr[root].rson!=-1) {
q[tail++]=tr[root].rson;
}
if(tr[root].lson!=-1) {
q[tail++]=tr[root].lson;
}
printf("%d",tr[root].num);
while(head!=tail) {
printf(" %d",tr[q[head]].num);
if(tr[q[head]].rson!=-1) {
q[tail++]=tr[q[head]].rson;
}
if(tr[q[head]].lson!=-1) {
q[tail++]=tr[q[head]].lson;
}
++head;
}
printf("\n");
}
return0;
}