给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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 <iostream> using namespace std ; #include <algorithm> #include <cstring> #include <cstdio> #include <map> #include <string> #include <math.h> #include <queue> int N, s = 0 ; int Q_ian[100], Z_hong[100] ; int a[100000], arr[100000] ; void Tree_cuna(int *qian, int *zhong, int n, int ind) { if(n == 0) return ; //长度为0 返回 int L = 0; while(qian[0] != zhong[L]) L++ ; a[ind] = qian[0] ; Tree_cuna(qian+1, zhong, L, ind*2) ; Tree_cuna(qian+L+1, zhong+L+1, n-L-1, ind*2+1) ; } void Mirror_Tree() { queue<int> q; q.push(1) ; while(!q.empty()) { int p = q.front() ; q.pop() ; arr[s++] = a[p] ; if(a[p*2+1] != 0) q.push(p*2+1) ; if(a[p*2] != 0) q.push(p*2) ; } } void test01() { cin >> N ; for(int i=0; i<N; i++) { cin >> Z_hong[i] ; } for(int i=0; i<N; i++) { cin >> Q_ian[i] ; } Tree_cuna(Q_ian, Z_hong, N, 1) ; Mirror_Tree() ; for(int i=0; ; i++) { if(arr[i] == 0) break ; if(i==0) printf("%d",arr[i]) ; else printf(" %d", arr[i]) ; } } int main(void) { test01() ; system("pause") ; return 0 ; }
运行结果：
