给定preOrder和inOrder序列，可能有多少个水平订单BST序列? [英] How many level order BST sequences are possible given a preOrder and inOrder sequence?

问题描述

当我尝试打印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序列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！