algorithm - 我们可以降低构建二叉树的时间复杂度吗？

Question

在我昨天的采访中，有人问我从给定的中序和前序/后序构建二叉树的时间复杂度。

我想出了偏斜树，它需要 O(N^2)，如果我们能保证平衡的二叉树，那么我们可以在 O(N log N) 内完成。

但是，为了回复唯一性，我想到了一个可以在 O(N) 时间内完成的想法。我给出的原因是

1. 在复杂度为O(N)的哈希表中，将中序遍历的所有节点一一放入。

2. 在哈希表中搜索特定节点可以在分摊的 O(1) 中完成。

3. 总时间复杂度理论上可以减少到 O(N)。 (其实我还没实现)

所以，我的回复是否正确，结果尚未公布。

Answer 1

可以在O(N)时间和O(N)空间内完成(对于倾斜的二叉树)，但不是存储中序遍历的元素，将元素的索引存储在哈希表中。那么下面的算法应该可以工作:

Function buildTree (in_index1, in_index2, pre_index1, pre_index2)
   root_index = hashEntry [pre-list[pre_index1]]
   createNode (root)
   root->leftChild = buildTree (in_index1, root_index-1, pre_index1 + 1, pre_index1 + (root_index-in_index1))
   root->rightChild = buildTree (root_index+1, in_index2, pre_index1 + (root_index-in_index1) + 1, pre_index2)
   return root

注:以上是基本思路。对于递归调用，您需要更仔细地获取正确的索引。