如何由前序与中序遍历推导后序遍历？附实例求解困惑

一、三种遍历的核心规则 #

• 前序遍历：根节点 → 左子树遍历 → 右子树遍历
• 中序遍历：左子树遍历 → 根节点 → 右子树遍历
• 后序遍历：左子树遍历 → 右子树遍历 → 根节点

二、前序+中序推导后序的通用步骤 #

核心逻辑：前序序列的首个元素是当前子树的根，用这个根在中序序列中划分出左、右子树的范围，再递归处理左右子树，最后拼接左后序、右后序、根节点得到结果。
具体操作：

1. 取当前前序序列的第一个元素作为当前子树的根
2. 在中序序列中定位该根节点，左侧元素为左子树的中序序列，右侧为右子树的中序序列
3. 根据左子树的元素数量，在前序序列中截取根节点后的对应长度片段，作为左子树的前序序列；剩余部分为右子树的前序序列
4. 递归处理左子树，得到左子树的后序序列
5. 递归处理右子树，得到右子树的后序序列
6. 拼接：左子树后序 + 右子树后序 + 当前根节点，即为当前子树的后序序列

三、针对本题的推导过程 #

给定：

• 前序序列：ABCEIFJDGHKL
• 中序序列：EICFJBGDKHLA

逐步推导： #

1. 整棵树的根：前序首个元素是A，在中序序列中A位于末尾，说明A没有右子树，左子树的中序序列为EICFJBGDKHL，前序序列为BCEIFJDGHKL
2. 左子树（根为B）：
   • 中序序列中B的位置划分出左子树EICFJ、右子树GDKHL
   • 左子树前序序列为CEIFJ（前序中B之后的5个元素，对应中序左子树的5个元素），右子树前序序列为DGHKL
3. B的左子树（根为C）：
   • 中序序列中C划分出左子树EI、右子树FJ
   • 左子树前序EI：根为E，中序中E右侧是I，说明E的右子树是I，后序为I E
   • 右子树前序FJ：根为F，中序中F右侧是J，说明F的右子树是J，后序为J F
   • 拼接得C子树的后序：I E J F C → IEJFC
4. B的右子树（根为D）：
   • 中序序列中D划分出左子树G、右子树KHL
   • 左子树前序G：后序为G
   • 右子树前序HKL：根为H，中序中H左侧是K、右侧是L，H的左子树K后序K，右子树L后序L，拼接得H子树后序K L H → KLH
   • 拼接得D子树的后序：G K L H D → GKLHD
5. B子树的后序：IEJFC + GKLHD + B → IEJFCGKLHDB
6. 整棵树的后序：IEJFCGKLHDB + A → IEJFCGKLHDBA

对比选项，选项D为正确结果。

内容的提问来源于stack exchange，提问作者Zingerlenga