algorithm - 从 Just Inorder Traversal 中查找预序？

Question

我遇到了一个中考题，那是 4 天前的，我无法理解它!

假设我们在对一棵树进行中序遍历时得到了答案，那么我们如何在先序遍历的情况下找到解决方案。我有以下示例:当按顺序遍历树时 E A C K F H D B G;

前序遍历会返回什么？

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

谁能以学习的方式帮助我？

编辑:我知道答案是:FAEKCDHGB。但是这是怎么计算的呢？

Answer 1

所以顺序是:

E A C K F H D B G

并且预订必须来自:

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

您应该继续为这些选项中的每一个绘制树，同时使其适合中序遍历，并查看哪一个是可能的。

为此，对于前序遍历中的每个字符，围绕该字符将中序遍历分成两部分。

一个。

我们知道 F 一定是根。拆分围绕 F 的中序遍历:

        | F | 
 E A C K     H D B G

前序遍历中的下一个字符是A。围绕A拆分包含A的子树:

            | F | 
     | A |        H D B G
    E     C K

下一个是E。没什么可分的。接下来是K:

            | F | 
     | A |        H D B G
    E     C
            K

下一个是C。没有什么可分割的。

下一个是D:

            | F | 
     | A |        | D |
    E     C      H     B G
            K

下一个是B:

            | F | 
     | A |        | D |
    E     C      H     B 
            K            G

我们已经完成了，不会有更多的 split 可能。现在在这棵树上运行前序遍历，你会得到:

F A E C K D H B G

这不是我们的出发点，所以我们得出了一个矛盾。所以它不能是a。对其他人做同样的事情。