从inorder和preorder遍历构造二叉树的时间复杂度

给定这是从inorder和preorder遍历构造树的代码。 我无法弄清楚他们是如何达到O（n ^ 2）时间复杂度的。 有任何想法吗？ 我看到在顺序序列中搜索索引将是O（n），其余的如何计算？

Answer 1

O(N^2)复杂度是由于对于Preorder遍历中的每个项目（其中有N ），您必须在Inorder遍历中搜索其分区（再次有N个）。

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

以他们给出的示例为例，进行以下遍历（Inorder then Preorder）：

 Inorder: DBEAFC Preorder: ABDECF 

现在这是他们被放置的网格：

  DBEAFC A + + + A | | | +--------------+ | B|F + B | F | +---------+ -----+ DE|CDEC 

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

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

例如，考虑这个树，其中preorder和inorder遍历是相同的：

 Inorder: DBEAFC Preorder: DBEAFC DBEAFC DD | | | | | -----+ | | | | BB | | | | -----+ | | | EE | | | -----+ | | AA | | -----+ | FF | -----+ CC 

这是最糟糕的情况，你看，网格中有N*N位置需要检查。 因此在最坏的情况下，存在N*N时间复杂度。

Answer 2

你正在遍历递归内的整个preorder数组，并在每个堆栈帧中搜索inorder遍历数组中的数字。 所以O(N*N) = o(N^2) 。

Answer 3

你是绝对正确的，因为在inorder数组中搜索将花费O（n）时间

在最坏的情况下T（n）= T（n-1）+ O（n）

解决这个问题我们得到T（n）= O（n²）