c++ - 从中序和先序遍历构造二叉树的时间复杂度

Question

给定Here是从中序遍历和先序遍历构建树的代码。我无法弄清楚他们是如何达到 O(n^2) 时间复杂度的。有任何想法吗？我看到在中序序列中搜索索引将是 O(n)，它的其余部分是如何计算的？

Answer 1

O(N^2) 的复杂性源于这样一个事实，即对于 Preorder 遍历中的每个项目(其中有 N)，您必须搜索它在中序遍历中的分区，(同样有 N 个)。

粗略地说，您可以将此算法视为将节点放置在网格上，其中中序遍历提供 x 坐标，先序遍历提供 y 坐标:

以他们给出的例子为例，进行以下遍历(Inorder 然后 Preorder):

Inorder: DBEAFC
Preorder: ABDECF

现在这是放置它们的网格:

     D    B    E    A    F    C
A    +    +    +    A    |    |
     |    +--------------+    |
B|F  +    B    |         F    |
     +---------+         -----+
DE|C D         E              C

现在，算法需要知道在网格中放置每个节点的位置，只需将节点放在网格中 x 和 y 坐标相同的位置即可。

在这种情况下，看起来网格的大小实际上是 NlogN，这将导致遍历网格的复杂度为 NlogN(因此 NlogN 算法的时间复杂度)但是这棵树是平衡的。在最坏的情况下，您的树实际上可能是一个链表。

例如考虑这棵树，其中前序和中序遍历是相同的:

Inorder: DBEAFC
Preorder: DBEAFC

     D    B    E    A    F    C
D    D    |    |    |    |    |
     -----+    |    |    |    |
B         B    |    |    |    |
          -----+    |    |    |
E              E    |    |    |
               -----+    |    |
A                   A    |    |
                    -----+    | 
F                        F    |
                         -----+
C                             C

这是最坏的情况，您看，网格中有 N*N 个位置需要检查。所以在最坏的情况下，有一个N*N的时间复杂度。