運(yùn)用分治算法根據(jù)中序遍歷和后序遍歷建立二叉樹(shù):

例題:

L2-3 浪漫側(cè)影

“側(cè)影”就是從左側(cè)或者右側(cè)去觀察物體所看到的內(nèi)容。例如上圖中男生的側(cè)影是從他右側(cè)看過(guò)去的樣子，叫“右視圖”；女生的側(cè)影是從她左側(cè)看過(guò)去的樣子，叫“左視圖”。

520 這個(gè)日子還在打比賽的你，也就抱著一棵二叉樹(shù)左看看右看看了……

我們將二叉樹(shù)的“側(cè)影”定義為從一側(cè)能看到的所有結(jié)點(diǎn)從上到下形成的序列。例如下圖這棵二叉樹(shù)，其右視圖就是 { 1, 2, 3, 4, 5 }，左視圖就是 { 1, 6, 7, 8, 5 }。

于是讓我們首先通過(guò)一棵二叉樹(shù)的中序遍歷序列和后序遍歷序列構(gòu)建出一棵樹(shù)，然后你要輸出這棵樹(shù)的左視圖和右視圖。

輸入格式：

輸入第一行給出一個(gè)正整數(shù)?N?(≤20)，為樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)。隨后在兩行中先后給出樹(shù)的中序遍歷和后序遍歷序列。樹(shù)中所有鍵值都不相同，其數(shù)值大小無(wú)關(guān)緊要，都不超過(guò)?int?的范圍。

輸出格式：

第一行輸出右視圖，第二行輸出左視圖，格式如樣例所示。

輸入樣例：

8 6 8 7 4 5 1 3 2 8 5 4 7 6 3 2 1

輸出樣例：

R: 1 2 3 4 5 L: 1 6 7 8 5