问题描述
当我尝试打印BST级时，此问题提示了我.
When I am trying to print level Order of BST, this question prompted me.
这是
Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8
具有以上 pre_order 和 In_order 的BST的级别订购顺序为 [4、2、6、1、3、5、7、8]
A level order sequence for a BST with above pre_order and In_order is[4, 2, 6, 1, 3, 5, 7, 8]
但是，对于相同的预购订单，此级别订购序列似乎是可能的. [4、1、5、2、6、3、7、8] .我不知道我正在尝试解决这个问题.
However, for the same Pre-order an In-order sequence this level order sequence seems possible. [4, 1, 5, 2, 6, 3, 7, 8]. I don't know how. I am trying to figure this out.
我无法在纸质(图纸)中构造满足所有pre_order，In-order和Level Order序列的BST.
I am unable to construct BST in paper (drawing) that satisfies all the pre_order, In-order and level order sequences.
推荐答案
如果同时进行有序遍历和前/后序之一，则足以重建二叉树.此外，对于BST(二元 search 树)而言，仅订购或订购就足够了.
If you have in-order traversal together with one of pre/post-order, that is enough to reconstruct a binary tree. Moreover, in case of BST (binary search tree), post-order or pre-order alone is sufficient.
在您的情况下，根据预购代码 4、1、2、3、5、6、7、8 重建BST可获得以下BST:
In your case, reconstructing a BST from pre-order 4, 1, 2, 3, 5, 6, 7, 8 gives the following BST:
4
/ \
1 5
\ \
2 6
\ \
3 7
\
8
再次给出唯一的级别顺序遍历 [4,1,5,2,6,3,7,8] .
which gives, again unique, level-order traversal [4,1,5,2,6,3,7,8].
另请参阅:
这篇关于给定preOrder和inOrder序列，可能有多少个水平订单BST序列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！