我不确定遍历是如何工作的以及它呈现的顺序
考虑遍历一棵树
预购 --> ABCEIFJDGHKL 顺序 --> EICFJBGDKHLA
以下哪项是正确的后序遍历？
A) EIFJCKGLHDBA
B) FCGKLHDBUAE
C) FCGKLHDBAEIJ
D) IEJFCGKLHDBA
我试着画出图表，但它与问题呈现的顺序不一样
前序序列总是先列出根，所以树的根是 A。由于后序必须列出根 last，我们已经可以删除潜在的答案 (B) 和 (C)，因为那些最后一个位置没有A。
中序首先列出根的左子树的节点，然后是根，然后是右子树的节点。由于 A 在中序序列中最后出现，所有其他节点都在左子树中。
这意味着左子树的预序序列为 BCEIFJDGHKL（没有 A 的原始预序），因此 B 是它的根。所以我们有：
A
/ \
B -
扩展B： 在中序序列中，我们在中途找到B，因此它的左子树由EICFJ组成，右子树由GDKHL组成。预序将左子树列为 CEIFJ，因此 C 是该子树的根。预序将右子树列为 DGHKL，因此 D 是该子树的根。这给了我们：
A
/
B
/ \
C D
展开C： 在中序序列EICFJ中，C的位置表示它的左子树由EI组成，右子树由FJ组成。 EI 的预序也是 EI，所以 E 是 C 的左孩子。FJ 的预序也是 FJ，所以 F 是 C 的右孩子：
A
/
B
/ \
C D
/ \
E F
展开E和F： 在中序序列EI中，E的位置表明I是它的右孩子。在中序序列FJ中，F的位置表明J是它的右孩子：
A
/
B
/ \
C D
/ \
E F
\ \
I J
展开D： 在中序序列GDKHL（见“展开B”）中，D的位置表示G是它的左孩子，KHL是它右子树中的节点。 KHL 的预序是 HKL，所以 H 是右子树的根：
A
/
_B_
/ \
C D
/ \ / \
E F G H
\ \
I J
展开H： 中序序列中KHL中间有H，所以剩下的K和L放在哪里就很清楚了
A
/
_B_
/ \
C D
/ \ / \
E F G H
\ \ / \
I J K L
此时可以直观地确认这棵树具有给定的前序和中序遍历。我们也可以读到后序遍历，即IEJFCGKLHDBA，所以正确答案是选项(D)。
o 确定正确的后序遍历，我们需要先了解每次遍历时访问节点的顺序。在前序遍历中，首先访问根节点，然后是左子树，然后是右子树。在中序遍历中，首先访问左子树，然后是根节点，然后是右子树。
为了获得后序遍历，我们首先访问左子树，然后是右子树，最后是根节点。 从根节点 A 开始，我们可以通过访问左子树，然后是右子树，最后是根节点来按后序遍历树。得到的后序遍历是：
C I F J D G K L H B E A
在提供的选项中，只有选项 A) EIFJCKGLHDBA 匹配此后序遍历。因此，正确答案是 A)。 :