如何從給定的遍歷中找到二叉樹？

Question

如何從給定的遍歷方法（inorder，post-order或pre-order）中找到二叉樹？

Answer 1

維基百科的文章中序，後序，前序遍歷樹是在這裏：

http://en.wikipedia.org/wiki/Tree_traversal。

您正在查找的樹開始於與您的搜索詞匹配的節點。

Answer 2

如果你想使用遍歷結果恢復原始樹，那麼我對你有一些壞消息 - 沒有明確的解決方案。將會有幾棵樹可以產生相同的遍歷結果。

例如，對於序遍歷以下的樹木會產生相同的結果：1, 2, 3

2   3  1 
/\  /  \ 
    1 3  2   2 
      /   \ 
      1    3 

Answer 3

無法通過它只有一個遍歷（中序，預購或後序）做到這一點。

這是可以做到。如果一棵樹的中序&序遍歷給出：

1. 序的第一個元素將是樹的根。 （假設它是A）
2. Inorder中的Searc root所以所有左邊的節點都是左子樹的Inorder和右子樹的Inorder。計算根節點左側的節點數量L.
3. 從第二個節點的後序將是左子樹的前序，之後是右子樹的前序。

因此，我們找到了根元素，並將我們的Inorder排序到左子樹的Inorder，右子樹的Inorder和Pre子到左子樹的預定義以及右子樹的預序中。所以我們可以通過遞歸來做到這一點，直到只剩下一個節點。

同樣，我們可以爲Inorder和Postorder進行操作，其中root將是後單的最後一個元素。

Answer 4

（好吧，既然我們已經決定，amended question應該在這裏，張貼我的答案也一樣）

二叉樹的後序和中序遍歷給出below.Is有可能獲得來自這些遍歷的唯一二叉樹？

這是可能的。

在後序遍歷（左右根）中，整棵樹的根節點總是最後一個（在你的情況下它是A）。在遍歷（左 - 右）中，根之前的節點屬於左子樹，根之後的節點 - 右邊的節點。由於我們已經確定了根，所以我們可以確定左子樹和右子樹中的節點。

確定後，我們可以在後序列表中分開左右子樹。所以，現在我們已經確定了左右子樹和根節點：

postorder: left|right|root 
inorder : left|root|right 

現在我們只需要遞歸構造左右子樹。鰭。