題面
給出一棵二叉樹的中序排列與后序排列，求出它的先序排列，（約定樹結點用不同的大寫字母表示，長度≤8），
輸入格式
2行，均為大寫字母組成的字串，表示一棵二叉樹的中序排列與后序排列，
輸出格式
1行，表示一棵二叉樹的先序排列，
樣例
輸入
BADC
BDCA
輸出
ABCD
前置知識
先序遍歷
若二叉樹為空，則空操作，否則：
訪問根結點、先序遍歷左子樹、先序遍歷右子樹
先序遍歷此圖結果為：124753689
中序遍歷
若二叉樹為空，則空操作，否則：
中序遍歷左子樹、訪問根結點、中序遍歷右子樹
中序遍歷上圖結果為：742513869
后序遍歷
若二叉樹為空，則空操作，否則：
后序遍歷左子樹、后序遍歷右子樹、訪問根結點
后序遍歷上圖結果為：745289631
思路分析
我們可以發現，一棵樹后序排列的最后一位就是這棵樹樹的根節點，以樣例為例，后序排列BDCA中最后一位為A，因此這棵樹的根節點為A，
我們又可以發現，在一棵樹的中序排列中，這棵樹的根節點將它的中序排列分為兩部分，即此根節點的左子樹和它的右子樹，同樣以樣例為例，中序排列BADC被根節點分為兩部分，即B和DC兩棵子樹，
那么，我們只需要繼續以同樣的方法，遞回尋找兩棵子樹的左子樹和右子樹就可以了，
代碼實作中的難點
如何快速確定根節點在中序排列中的位置？
關于這一點我們當然可以一個一個地找過去，但為了讓程式跑得更快，我們可以模仿映射的思想，建立一個陣列，記錄后序排列中的每一位在中序排列中的位置（具體實作看代碼）
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
char mid[10],post[10];
//mid陣列記錄中序排列，post陣列記錄后序排列
//除了打暴力最好不要用string
int z[10],m[10],p[10];
//z陣列做中轉使用，m陣列記錄mid陣列的內容，p陣列記錄post陣列的每一位在mid陣列中的位置
void find(int start,int end,int kai,int jie){
//start和end記錄我們正在找的mid陣列的范圍
//kai（開頭）和jie（結尾）記錄我們正在找的post陣列的范圍
if(start>end||kai>jie)return;
//如果開頭大于結尾，就回傳
if(start==end||kai==jie){
printf("%c",mid[p[jie]]);
return;
}
//如果開頭等于結尾，那此節點一定沒有兒子，輸出當前節點并回傳
printf("%c",mid[p[jie]]);
//前面說過后序排列的最后一位就是當前樹的根節點，所以p[jie]就是根節點在mid陣列中的位置
//開頭小于結尾，那就輸出當前節點然后再去尋找此節點的左兒子和右兒子
find(start,p[jie]-1,kai,kai+p[jie]-start-1);
//求左子樹的范圍，然后遞回尋找左兒子
find(p[jie]+1,end,kai+p[jie]-start,jie-1);
//求右子樹的范圍，然后遞回尋找右兒子
}
int main(){
scanf("%s%s",mid+1,post+1);
//輸入時下標從1開始（主要是因為我比較毛病）
int len=strlen(mid+1);
//輸入時下標從1開始那么計算字串長度時也要加1
for(int i=1;i<=len;i++){
m[i]=mid[i]-'A'+1;
//將每一位轉成數字以方便處理（是的，我很毛病）
z[m[i]]=i;
//z陣列記錄m陣列每一位的位置（這一步是為了方便后面記錄post數字）
}
for(int i=1;i<=len;i++){
p[i]=z[post[i]-'A'+1];
//記錄post陣列的每一位在mid陣列中的位置
//z：我滴任務完成啦！
}
find(1,len,1,len);
//開始遞回
return 0;
}如此就完成啦~
Lo問我為什么看星星，我覺得銀河和代碼是同一種東西，這也是一種回答，————Co轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/449715.html
標籤：C++