我遇到了一个中考题,那是 4 天前的,我无法理解它!
假设我们在对一棵树进行中序遍历时得到了答案,那么我们如何在先序遍历的情况下找到解决方案。我有以下示例:当按顺序遍历树时 E A C K F H D B G
;
前序遍历会返回什么?
a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG
谁能以学习的方式帮助我?
编辑: 我知道答案是:FAEKCDHGB。但是这是怎么计算的呢?
最佳答案
所以顺序是:
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。对其他人做同样的事情。
关于algorithm - 从 Just Inorder Traversal 中查找预序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29046384/