考慮到preOrder和inOrder序列，有多少級別的BST序列是可能的？

Question

當我試圖打印BST級別的順序時，這個問題促使我。

下面是用於與上述pre_order和In_order一個BST一個

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8 
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8 

A級序是 [4, 2, 6, 1, 3, 5, 7, 8]

然而，對於相同的預購一個在層序這個水平序似乎可能。 [4, 1, 5, 2, 6, 3, 7, 8]。我不知道如何。我正試圖弄清楚這一點。

我無法在紙張（圖紙）中構建BST，以滿足所有預先訂單，有序和水平訂單序列。

Answer 1

如果你有順序遍歷前/後的順序之一，這足以重建一棵二叉樹。此外，在BST的情況下（二進制搜索樹），後單或預訂單就足夠了。

在你的情況，重建從預購4, 1, 2, 3, 5, 6, 7, 8一個BST給出以下BST：

 4 
/ \ 
    1  5 
    \  \ 
    2  6 
    \  \ 
     3  7 
      \ 
       8 

賦予，又獨特，層次序遍歷[4,1,5,2,6,3,7,8]。

參見：

• Reconstructing binary trees from tree traversals

Answer 2

以下組合將產生獨一無二的二叉樹（可BST）。

Inorder and Preorder. 
Inorder and Postorder. 
Inorder and Level-order. 

所以你的情況序&預購給出這將產生唯一的二進制樹是BST你的情況如此級別順序將是該樹是唯一的。

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8 
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8 

SO樹將

level 0- 4 
level 1- 1,5 
level 2- 2,6 
level 3- 3,7 
level 4- 8 

等級順序是

4,1,5,2,6,3,7,8

在排序總是會有獨特的等級順序遍歷