Ocaml help tree traversal

Question

問題描述：

R. Borist教授研究樹木。他保留了所有他喜歡的樹的前序，前序和後序遍歷記錄。然而，他的辦公室發生的火災摧毀了他存放順序遍歷的文件櫃。他仍然有他所有最喜歡的樹的前序和後序遍歷，這是足夠的信息來重建丟失的inorder遍歷嗎？

您必須爲以下任務設計和實現一個程序：輸入將由 兩列數字組成。第一個列表是某棵樹T的前序遍歷。第二個列表是對同一棵樹T的後序遍歷。輸出應該是T的序遍歷。如果輸入不確定唯一的樹，則任何一致的inorder遍歷可以退貨。

如果它幫助設計你實現，你可以假設：

• 沒有樹有超過1000個節點。
• 沒有樹爲多個節點使用相同的標籤。
• 節點的標籤是從0到10,000的數字。

的樣本數據

Input: 
2 6 7 1 11 8 5 10 3 4 9 
7 8 5 11 10 1 6 4 9 3 2 
Output: 
7 6 8 11 5 1 10 2 4 3 9 

提示

給出一個在樹的前序後序&遍歷，你可以推斷出哪個元素是 根源在哪裏？哪些元素必須來自左側的子樹？從正確的子樹？遞歸。

首先解決樹中的每個節點都保證有2個或者0個 孩子的問題。一些節點只有一個孩子的情況有點棘手。

注意

在你的書面記錄，你並不需要分析解決方案的效率/運行時間（這將是未來項目的要求）。但是要分析它的正確性;即清楚地解釋爲什麼你的算法是正確的。

---

問題我馬上就要理解如何從前置和後置構建inorder遍歷。我試圖找出一些有5個和7個節點的小例子，就像提示一樣，但沒有看到這個模式。幫幫我！

UPDATE 所以我想我想出瞭如何想出另外兩個列表的inorder遍歷。我需要知道左子樹右子樹和根。根始終在帖子訂單的末尾和預訂的開始。左邊的子樹可以在這兩個列表中找到，但是我認爲從後序得到的結果更容易使它在前面。其次是右側子樹和根。在預定順序中，左子樹在根子之後，右子樹。我只需要幫助把想法變成代碼...

你可以使用ocaml中的索引提取特定元素嗎？

我很難分辨在子樹開始和結束，怎麼可以拉出信息，並返回一個列表出了兩

像我知道的X名單:: XS翻出第一要素了名單和這樣的簡單的事情......

任意一個幫助或可提供提示和建議我只考慮一個情況下，我有兩個或沒有節點作爲孩子

更新：我沒有用ocaml編寫程序我可以使用任何我想要的語言。我熟悉java，所以我想在java中實現解決方案。

我有一個很好的瞭解如何獲取所需信息的形式先和後順序列表打造以讓我覺得我解決了這個邏輯的一部分，但需要幫助把我的想法轉換成Java代碼任何一個可以幫助？

Answer 1

即使問題描述沒有明確說明，但從提示中可以清楚地看到我們正在處理二叉樹。

提示很好：找到樹的根，然後找到左側子樹的根和右側的根。

刪除根後，在可以剪切列表的節點列表中查找一個位置：剪切前的節點來自左側子樹，剪切後的節點來自右側子樹。

制定出像你這樣的小例子是個好主意。

具體回答「瞭解如何從前置和後置構建inorder遍歷」：首先從前置和後置遍歷中重建樹，然後從樹中構建inorder遍歷。