建立二叉樹出給定遍歷

Question

我解決我的家庭作業的數據結構和算法課程，我碰到這個問題來了：

「給定兩個穿越的方法可以預購和後序，預購和有序，後序和有序，我們可以提取多少二叉樹？「

現在我知道你當然無法從一個遍歷順序中找到二叉樹，但是這兩個遍歷中的哪一個只會給你一個二叉樹？如何 ？以及那些沒有舉例說明一棵二叉樹的地方，它們有多少二叉樹可以作爲例證，我們如何計算這個數字？

Answer 1

我相信this source很有用。樹的前置和後置遍歷不足以在沒有進一步限制的情況下唯一地重構它。然而，一個算法展示瞭如何從它的後序重構樹並按順序進行並且最後一種情況有些對稱我認爲這是算法證明了一棵樹可以從它的inorder和任何其他遍歷中唯一地重構。