已知二叉树前序与中序遍历，如何输出后序遍历？求简化解法

核心逻辑基于三个遍历的特性：

• 前序遍历：根 → 左子树 → 右子树（第一个元素必为整棵树的根）
• 中序遍历：左子树 → 根 → 右子树（根的位置可以拆分出左右子树的范围）
• 后序遍历：左子树 → 右子树 → 根（我们最终要输出的顺序）

分步拆解（用实例说明） #

假设已知：

• 前序遍历：[1, 2, 4, 5, 3, 6]
• 中序遍历：[4, 2, 5, 1, 6, 3]

步骤1：确定根节点

前序遍历的第一个元素就是当前树的根，这里是 1。

步骤2：拆分左右子树

在中序遍历中找到根节点1的位置（索引为3）：

• 根左边的元素[4,2,5]是左子树的中序遍历
• 根右边的元素[6,3]是右子树的中序遍历

步骤3：提取左右子树的前序遍历

左子树的节点数量等于中序左子树的长度（3个），因此前序遍历中根后面的前3个元素就是左子树的前序：[2,4,5]
剩下的元素就是右子树的前序：[3,6]

步骤4：递归处理左右子树

对左子树（前序[2,4,5]、中序[4,2,5]）和右子树（前序[3,6]、中序[6,3]）重复上述步骤：

• 左子树的根是2，拆分出左子树[4]和右子树[5]，最终左子树的后序是[4,5,2]
• 右子树的根是3，拆分出左子树[6]，最终右子树的后序是[6,3]

步骤5：拼接最终后序遍历

按「左子树后序 → 右子树后序 → 根」的顺序拼接，得到整棵树的后序：[4,5,2,6,3,1]

简化伪代码实现 #

def pre_in_to_post(preorder, inorder):
    # 递归终止条件：空树返回空列表
    if not preorder:
        return []
    
    # 取当前树的根节点（前序第一个元素）
    root = preorder[0]
    # 找到根在中序遍历中的位置
    root_pos = inorder.index(root)
    
    # 拆分左子树的前序、中序
    left_pre = preorder[1 : 1 + root_pos]
    left_in = inorder[:root_pos]
    # 拆分右子树的前序、中序
    right_pre = preorder[1 + root_pos :]
    right_in = inorder[root_pos + 1 :]
    
    # 递归处理左右子树，拼接后序结果
    return pre_in_to_post(left_pre, left_in) + pre_in_to_post(right_pre, right_in) + [root]

注意事项 #

• 该方法的前提是二叉树中没有重复节点，否则中序遍历中无法唯一确定根的位置。
• 递归的本质是不断缩小问题规模：每次处理一棵更小的子树，直到子树为空。

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