題目：

給定一棵二叉樹的中序遍歷和前序遍歷，請你先將樹做個鏡面反轉，再輸出反轉后的層序遍歷的序列。所謂鏡面反轉，是指將所有非葉結點的左右孩子對換。這里假設鍵值都是互不相等的正整數。

輸入格式：

輸入第一行給出一個正整數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.鏡面反轉：這個其實就只要在遞歸的時候先遞歸右樹，再遞歸左樹就好；
2.層序遍歷：

不同的層放在一個vector中，每層可以區分開，在遞歸過程中，當做一個完全滿二叉樹來看，初始化vector數組為-1（表示二叉樹節點都為Null），將每個值放在對應節點上，輸出時，特判一下-1（即為空）的狀態即可。
3.復習：創建vector容器的三種方式
（1）不指定元素個數：

vector<int>v;

（2）指定容器的大小

vector<int>v(10);

（3）指定容器的大小，且每個元素具有指定的初始值。

vector<double>(10,8.6);

4.利用遞歸，從前序一個個元素開始，root=1； 在中序中找到$a[root]==b[i]$,
然后將中序分為兩部分，$b[1.....i?1]和b[i+1.....n]$,然后分別遍歷這兩
部分，直到這兩部分元素為0(x>y) 或1個（x==y）；

• 左子樹 ,左子樹范圍必定在x到i-1之間，下一個根的位置在root+1
• 右子樹，右子樹范圍必定在i+1到y之間，根的位置就是(i-x)是左子樹
  的大小，相當于root位置往后移左子樹的個數再加一

前序遍歷：根左右
中序遍歷：左根右
后序遍歷：左右根

AC代碼：

#include <iostream> #include<stdio.h> #include <vector> #define N 31 using namespace std; int a[N],b[N]; vector<int> ve(100000,-1); void build(int x,int y,int root,int step)/**x,y為左子樹或右子樹的區間，root為根節點，step為當前根節點的位置（滿二叉樹）*/ {if(x>y) return;ve[step]=a[root];/**記錄當前根節點的位置*/int i;for(i=x;i<=y;++i){if(a[root]==b[i])break;}build(i+1,y,root+(i-x)+1,step*2+1);build(x,i-1,root+1,step*2+2);/**鏡面這個其實就只要在遞歸的時候先遞歸右樹，再遞歸左樹就好*/ } int main() {int n;cin>>n;for(int i=1;i<=n;++i)cin>>b[i];for(int i=1;i<=n;++i)cin>>a[i];build(1,n,1,0);int cnt=0;for(int i=0;i<ve.size()&&cnt<=n;++i){if(ve[i]!=-1){if(i)cout<<" ";cout<<ve[i];++cnt;}}return 0; }

總結

以上是生活随笔為你收集整理的玩转二叉树 (25 分) 知中序遍历和前序遍历，求做个镜面反转后的层序遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。