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 ; } char 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 ) return 0 ; 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 ; return 0; }
加个正确的解答吧。完美AC的。
来源：http://blog.csdn.net/idealism_xxm/article/details/51584798
#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"); } return 0; }
查看28道真题和解析