使用給定的遍歷驗證二叉樹

Question

是否有可能確定序列中沒有二進制樹存在給定兩個遍歷（例如：一個順序和後序遍歷）？

我知道，後序遍歷的最後一個元素，或者是預遍遍的第一個元素，就是樹的根。使用這樣的基本事實，是否可以測試這些數組而不實際構建樹並查明它們是否生成相同的樹？

我有一個算法已經可以從這兩個序列（in和post）中構建一棵樹，但是我不想在預先測試數組的情況下運行算法。這將節省大量時間，而不是運行算法並在最後查找。

注意：這不一定是二叉搜索樹。二叉樹就足夠了。

Answer 1

我又開始了，因爲問題與我想象的有點不同。給定一個inorder和postorder遍歷，你可以找到是否有一棵樹可以生成它們兩個？

讓我們考慮這棵樹：

 a 
/ \ 
    b  e 
/\ /\ 
c d f g 

的遍歷是：

inorder: CBDAFEG 
postorder: CDBFGEA 

現在一些意見：

一個。後序中的最後一個節點始終是根節點。

b如果你知道根節點，你可以將一個inorder遍歷分爲左遍歷，右遍歷，右遍歷。

因此，您可以在不創建樹的情況下運行遞歸算法，以確定它們是否可以由同一棵樹生成。

像這樣：

鑑於木衛一和寶象兩個traverals，

如果它們是不同的長度則沒有樹的共同點。

如果相同的長度，則：

1. 取寶的最後一個節點 - 稱之爲R IN木衛一
2. 求R。如果沒有找到，則沒有共同的樹。

3. ř確定左和右子樹中，所以分割木衛一和Po的基於R的IO中的位置的界限：

   CBD甲FEG

   CDB FEG甲

（例如，一旦您知道左側子樹必須是3個節點長，並且右側sig樹也是3個長度的節點，則也可以以相同方式分割Po）

1. 在左側和右側子樹上遞歸地調用該算法。

Answer 2

我不認爲你可以在一般情況下這樣做，因爲你不能僅僅通過遍歷來確定樹的結構。那就是有很多樹生成相同的遍歷。

例如，這裏有兩棵樹有相同的順序遍歷。

A      A 
/\     /
B C     B 
        /
         C 

但是他們的順序遍歷是不同的。所以如果使用同一棵樹生成它們，就不可能說出按順序和後序遍歷。