題面

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供蕪湖縣網(wǎng)站建設(shè)、蕪湖縣做網(wǎng)站、蕪湖縣網(wǎng)站設(shè)計(jì)、蕪湖縣網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、蕪湖縣企業(yè)網(wǎng)站模板建站服務(wù)，10多年蕪湖縣做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

給出一棵二叉樹(shù)的中序排列與后序排列。求出它的先序排列。（約定樹(shù)結(jié)點(diǎn)用不同的大寫字母表示，長(zhǎng)度≤8）。

輸入格式

2行，均為大寫字母組成的字符串，表示一棵二叉樹(shù)的中序排列與后序排列。

輸出格式

1行，表示一棵二叉樹(shù)的先序排列。

樣例

輸入

BADC

BDCA

輸出

ABCD

前置知識(shí)

先序遍歷

若二叉樹(shù)為空，則空操作，否則：

訪問(wèn)根結(jié)點(diǎn)、先序遍歷左子樹(shù)、先序遍歷右子樹(shù)

先序遍歷此圖結(jié)果為：

中序遍歷

若二叉樹(shù)為空，則空操作，否則：

中序遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、中序遍歷右子樹(shù)

中序遍歷上圖結(jié)果為：

后序遍歷

若二叉樹(shù)為空，則空操作，否則：

后序遍歷左子樹(shù)、后序遍歷右子樹(shù)、訪問(wèn)根結(jié)點(diǎn)

后序遍歷上圖結(jié)果為：

思路分析

我們可以發(fā)現(xiàn)，一棵樹(shù)后序排列的最后一位就是這棵樹(shù)樹(shù)的根節(jié)點(diǎn)。以樣例為例，后序排列BDCA中最后一位為A，因此這棵樹(shù)的根節(jié)點(diǎn)為A。

我們又可以發(fā)現(xiàn)，在一棵樹(shù)的中序排列中，這棵樹(shù)的根節(jié)點(diǎn)將它的中序排列分為兩部分，即此根節(jié)點(diǎn)的左子樹(shù)和它的右子樹(shù)。同樣以樣例為例，中序排列BADC被根節(jié)點(diǎn)分為兩部分，即B和DC兩棵子樹(shù)。

那么，我們只需要繼續(xù)以同樣的方法，遞歸尋找兩棵子樹(shù)的左子樹(shù)和右子樹(shù)就可以了。

代碼實(shí)現(xiàn)中的難點(diǎn)

如何快速確定根節(jié)點(diǎn)在中序排列中的位置？

關(guān)于這一點(diǎn)我們當(dāng)然可以一個(gè)一個(gè)地找過(guò)去，但為了讓程序跑得更快，我們可以模仿映射的思想，建立一個(gè)數(shù)組，記錄后序排列中的每一位在中序排列中的位置（具體實(shí)現(xiàn)看代碼）

#include
#include
#include
#define ll long long
using namespace std;
char mid[10],post[10];
//mid數(shù)組記錄中序排列，post數(shù)組記錄后序排列
//除了打暴力最好不要用string
int z[10],m[10],p[10];
//z數(shù)組做中轉(zhuǎn)使用，m數(shù)組記錄mid數(shù)組的內(nèi)容，p數(shù)組記錄post數(shù)組的每一位在mid數(shù)組中的位置
void find(int start,int end,int kai,int jie){
//start和end記錄我們正在找的mid數(shù)組的范圍
//kai（開(kāi)頭）和jie（結(jié)尾）記錄我們正在找的post數(shù)組的范圍
    if(start>end||kai>jie)return;
    //如果開(kāi)頭大于結(jié)尾，就返回
    if(start==end||kai==jie){
        printf("%c",mid[p[jie]]);
        return;
    }
    //如果開(kāi)頭等于結(jié)尾，那此節(jié)點(diǎn)一定沒(méi)有兒子，輸出當(dāng)前節(jié)點(diǎn)并返回
    printf("%c",mid[p[jie]]); 
    //前面說(shuō)過(guò)后序排列的最后一位就是當(dāng)前樹(shù)的根節(jié)點(diǎn)，所以p[jie]就是根節(jié)點(diǎn)在mid數(shù)組中的位置
    //開(kāi)頭小于結(jié)尾，那就輸出當(dāng)前節(jié)點(diǎn)然后再去尋找此節(jié)點(diǎn)的左兒子和右兒子
    find(start,p[jie]-1,kai,kai+p[jie]-start-1);
    //求左子樹(shù)的范圍，然后遞歸尋找左兒子
    find(p[jie]+1,end,kai+p[jie]-start,jie-1);
    //求右子樹(shù)的范圍，然后遞歸尋找右兒子
}
int main(){
    scanf("%s%s",mid+1,post+1);
    //輸入時(shí)下標(biāo)從1開(kāi)始（主要是因?yàn)槲冶容^毛病）
    int len=strlen(mid+1);
    //輸入時(shí)下標(biāo)從1開(kāi)始那么計(jì)算字符串長(zhǎng)度時(shí)也要加1
    for(int i=1;i<=len;i++){
        m[i]=mid[i]-'A'+1;
        //將每一位轉(zhuǎn)成數(shù)字以方便處理（是的，我很毛?。?        z[m[i]]=i;
        //z數(shù)組記錄m數(shù)組每一位的位置（這一步是為了方便后面記錄post數(shù)字）
    }
    for(int i=1;i<=len;i++){
        p[i]=z[post[i]-'A'+1];
        //記錄post數(shù)組的每一位在mid數(shù)組中的位置
        //z：我滴任務(wù)完成啦！
    }
    find(1,len,1,len);
    //開(kāi)始遞歸
    return 0;
}

如此就完成啦~