如何通过预遍历和有序遍历构建二叉树

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

1. 如果数组的长度为1，则只需返回其中包含此单个项的叶节点即可。（这是递归基础。）（O（1））
2. 将第一个条目存储在预订数组中作为根节点。（O（1））
3. 在顺序数组中搜索该条目。（上））
4. 将字符放在顺序数组中根节点的左侧，并将其另存为字符数组。从预定数组中（根之后）取相同数量的字符。（O（n）或O（1）只是在周围抛出指针/索引时。）
5. 将字符放在根节点的右侧，并将其另存为字符数组。从预定数组中提取相同数量的字符（在第一部分之后–应该只是剩余部分）。（O（n）或O（1）只是在周围抛出指针/索引时。）
6. 从两个左侧的char数组递归生成一棵树。
7. 从两个正确的char数组递归生成一棵树。
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 +<--+
+---+