從兩個遍歷輸出創建二叉樹

Question

這是家庭作業，但由於某些原因，它不允許我添加作業標籤。

我們被分配一個實驗室的數據結構，其中最後一個問題問我們發現，會產生從給定的遍歷方法如下輸出二叉樹：

LRN: 12, 9, 4, 7, 1, 14, 8, 13, 10, 15, 11, 2, 5, 16, 6, 3 

和

LNR: 12, 3, 4, 9, 8, 1, 7, 14, 6, 13, 10, 16, 5, 15, 2, 11 

我已經確定了以下關於該樹的內容：

根節點是3.根節點離開孩子，只有樹的左邊孩子是12.根號des右邊的孩子是6.最右邊的節點是5.

不幸的是我被困在如何繼續。任何提示將不勝感激。

Answer 1

從後序（LRN），我們知道最後一個元素是根。我們可以找到有序的（LNR）。然後，我們可以從有序的角度確定根的左右子樹。

使用左側子樹的長度，我們可以在後序數組中識別左右子樹。遞歸地，我們可以建立樹。

檢查this鏈接。