如何从preorder和inorder遍历构建二叉树

Question

我正在做一个从预订和顺序遍历(每个节点中的一个字符串)构建二叉树的任务,并试图围绕如何构建实际的树包裹我的大脑.

以下是关于如何实现此目标的思考过程:

1. 将预订中的第一个条目存储为根节点
2. 搜索该条目的顺序.
3. 将字符放在根节点的左侧,并将它们保存为char数组.
4. 将字符放在根节点的右侧,并将它们保存为char数组.
5. 创建一个新树,以root作为父,其中2个子元素为左右char数组.
6. 继续递归,直到预订长度为0.

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

Answer 1

在构建新树之前执行递归.所以,你的列表看起来像这样:

1. 如果数组的长度为1,则只返回包含此单个项目的叶节点.(这是递归基础.)(O(1))
2. 将第一个条目存储在预订单数组中作为根节点.(O(1))
3. 在inorder数组中搜索该条目.(上))
4. 将字符放在inorder数组中根节点的左侧,并将它们保存为char数组.从预订单数组中获取相同数量的字符(在根之后).(O(n)或O(1)当只是抛出指针/索引时.)
5. 将字符放在根节点的右侧,并将它们保存为char数组.从预订单数组中获取相同数量的字符(在第一部分之后 - 应该只是剩余部分).(O(n)或O(1)当只是抛出指针/索引时.)
6. 从两个char数组递归地生成一个树.
7. 从两个正确的char数组递归地生成一个树.
8. 将两个树与根节点组合在一起.(O(1).)

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

在最坏的情况下,我们在树中的每个节点都有一个递归级别,达到复杂度O(n·n).

示例:预购ABCDEF,Inorder FEDCBA,树:

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