algorithm - 从 Just 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

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

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

一个。

我们知道F必须是根。拆分周围的中序遍历F：

        | F | 
 E A C K     H D B G

前序遍历中的下一个字符是A。拆分包含Aaround的子树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

我们已经完成了，不会再有分裂的可能了。现在在这棵树上运行前序遍历，你会得到：

F A E C K D H B G

这不是我们开始的，所以我们遇到了矛盾。所以不能是a。对其他人做同样的事情。

Answer 2

答案是不确定的。

看看这两棵树：

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

和：

   A
 /  \
E    C 
      \
       K
        \
         F 
          \
           H 
            \
             D 
              \
               B
                \
                 G

这两棵树有相同的中序遍历，但是第一个有 的前序遍历EACKFHDBG，而第二个有 的中序遍历AECKFHDBG

因此，给定一个中序遍历，有不止一个可能的二叉树适合该遍历。这是因为存在n!可能的排列（因此是按顺序遍历），而二叉树的数量要多得多。这保证（鸽笼原则）存在（至少一个）适合多棵树的有序遍历。

Answer 3

可能的 b 树之一是：

所以，前序遍历返回：

香港航空航天发展局

另一个是：

前序遍历给出：

HAEKCFBDG

还有一个是：

前序遍历给出：

KAECHFBDG

，这不是你的选择。欢迎任何人发表评论，因为我无法为给定的中序遍历提供任何其他二叉树..

我在考试中也有这个问题，但后来知道 b 是谷歌搜索该问题的答案。洛兹。