java - 如何从前序和中序遍历构建二叉树

Question

我正在做一项关于从前序和中序遍历(每个节点中的一个字符)构建二叉树的作业，我正在努力思考如何构建实际的树。

以下是我关于如何实现这一点的思考过程:

1. 将前序中的第一个条目存储为根节点
2. 在订单中搜索该条目。
3. 取根节点左边的char，保存为char数组。
4. 取根节点右边的char，保存为char数组。
5. 创建一棵新树，以根为父节点，其 2 个子节点为左右字符数组。
6. 继续递归直到前序长度为 0。

我已经完成了第 1-4 步，但我不太确定如何正确构建我的树，并且想知道是否有人有任何指示。谢谢。

Answer 1

在构建新树之前进行递归。因此，您的列表将如下所示:

1. 如果数组的长度为 1，则只返回一个包含该单个项目的叶节点。 (这是递归基础。)(O(1))
2. 将前序数组中的第一个条目存储为根节点。 (O(1))
3. 在中序数组中搜索该条目。 (O(n))
4. 取inorder数组中根节点左边的char，存为char数组。从前序数组中取出相同数量的字符(在根之后)。 (O(n) 或 O(1)，当只是抛出指针/索引时。)
5. 取根节点右边的chars，保存为char数组。从预序数组中取出相同数量的字符(在第一部分之后——应该只是剩余部分)。 (O(n) 或 O(1)，当只是抛出指针/索引时。)
6. 从两个左边的字符数组递归地生成一棵树。
7. 从两个右字符数组递归地生成一棵树。
8. 将两棵树与您的根节点结合起来。 (O(1).)

非递归部分总体上可以在 O(n) 内完成，并且每个递归级别对它们求和也是每个 O(n)。因此，总运行时间取决于递归级别的数量。如果你有一个近似平衡的树，深度是 O(log n)，因此我们得到 O(n · log n)。由于唯一必然较慢的部分是在中序数组中搜索根节点，我想如果我们对树有更多了解，我们可以进一步优化它。

在最坏的情况下，我们对树中的每个节点都有一个递归级别，复杂度为 O(n·n)。

示例:预购 ABCDEF、中购 FEDCBA、树:

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