有多少二叉樹可以滿足給定的前序遍歷和後序遍歷？

Question

例如

preorder-> 0,1,2

postorder-> 2,1,0

 0 
    /
    1 
/
    2 

     0 
    /
    1 
    \ 
     2 

     0 
     \ 
     1 
    / 
     2 

     0 
     \ 
     1 
     \ 
      2 

這些是4個二叉樹可能以上case.How許多樹是一般可用於任何前序和後序遍歷？

Answer 1

有兩種回答您的問題：

• 對於二進制樹的後序給予序和遍歷，你只能找到一棵樹。 （注意對二進制的強調！我只允許根具有2級）
  示例草圖在this answer中給出，您也可以在其中找到重建算法。

• 如果你的樹被允許有2級的內部節點，即只有一個孩子的節點，那麼你可以把它放在左邊或右邊，前後序中相應的子樹位置遍歷不會改變。所以如果你有k這樣的節點，你有2^k等價樹