從預購和後序遍歷中重建樹

Question

給定具有獨特元素的非二叉樹的前序遍歷和後序遍歷，我如何創建它們來自的樹？

例如

給定序= ABCDEF
和後序= BCEFDA

應該建立樹相當於
~~甲一個~~~~~
-/- |〜\〜 ~~
乙〜C〜d ~~
~~~~ /〜\ ~~
~~~Ë~~ F〜

（SOR關於波浪號的，這是唯一的方法，我可以弄清楚如何讓樹看起來是正確的，仍然是清晰可見的）

無論如何，我不要求代碼做到這一點，因爲它是一個家庭作業項目而代碼本身不是問題。我需要幫助的是比較兩個輸入的算法，以便它們可靠地創建適當的樹。

P.S.給定的樹可以是具有節點

TL的任何數量的（推測< = 26）或多或少複雜; DR
How do I use Pre-order and Post-order traversals to construct their original tree

Answer 1

遞歸+迭代求解

每級進程整個字符串傳遞給它

• 如果第一要素是相等的 - 刪除和添加作爲當前級別
• 的孩子如果第一個元素不等於 - 刪除第一個元素預購作爲家長，不僅如此，串到位置後才能元素被發現

調用空哨點作爲一個

父這會給你遞歸調用結果在最有可能的情況下。