从Inorder Traversal中寻找Preoder？

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

您应该继续为每个选项绘制树,同时使其适合于inorder遍历并查看哪个可能.

为此,对于前序遍历中的每个字符,将围绕该字符的inorder遍历拆分为两个.

一个.

我们知道F必须是根.拆分inorder遍历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

我们已经完成了,不会有更多的分裂.现在在这棵树上运行preorder遍历,你会得到:

F A E C K D H B G

这不是我们开始的,所以我们达成了矛盾.所以它不可能是一个.为其他人做同样的事情.