已知先序和中序求后序：3步推导法附实例详解

在二叉树中，有三种基本的遍历方式：前序遍历、中序遍历和后序遍历。前序遍历的顺序是：根节点-左子树-右子树；中序遍历的顺序是：左子树-根节点-右子树；后序遍历的顺序是：左子树-右子树-根节点。

当我们知道一个二叉树的前序遍历和中序遍历的结果时，我们可以通过以下3步推导法来求得后序遍历的结果：

1. 构建根节点与左子树、右子树的关系：

- 在中序遍历中，根节点将中序遍历的序列分为左子树序列和右子树序列。

- 根据前序遍历的顺序，我们可以知道第一个元素是根节点。

2. 递归处理左子树和右子树：

- 对左子树和右子树分别进行上述步骤，构建它们的根节点与左子树、右子树的关系，并求得它们各自的后序遍历结果。

3. 组合左子树、右子树与根节点的后序遍历结果：

- 根据后序遍历的顺序，左子树-右子树-根节点，将左子树、右子树的后序遍历结果与根节点组合，得到最终的后序遍历结果。

下面是一个具体的实例，假设我们有一个二叉树，其前序遍历为：[1, 2, 4, 5, 3, 6, 7]，中序遍历为：[4, 2, 5, 1, 6, 3, 7]。

1. 构建根节点与左子树、右子树的关系：

- 在中序遍历中，1将序列分为左子树序列[4, 2, 5]和右子树序列[6, 3, 7]。

- 根据前序遍历的顺序，我们知道第一个元素1是根节点。

2. 递归处理左子树和右子树：

- 对左子树[4, 2, 5]，其前序遍历为[2, 4, 5]，中序遍历为[4, 2, 5]。重复上述步骤，得到左子树的后序遍历为[4, 5, 2]。

- 对右子树[6, 3, 7]，其前序遍历为[3, 6, 7]，中序遍历为[6, 3, 7]。重复上述步骤，得到右子树的后序遍历为[6, 7, 3]。

3. 组合左子树、右子树与根节点的后序遍历结果：

- 根据后序遍历的顺序，左子树-右子树-根节点，将左子树[4, 5, 2]、右子树[6, 7, 3]的后序遍历结果与根节点1组合，得到最终的后序遍历结果为[4, 5, 2, 6, 7, 3, 1]。

当我们知道一个二叉树的前序遍历为[1, 2, 4, 5, 3, 6, 7]和中序遍历为[4, 2, 5, 1, 6, 3, 7]时，其后序遍历为[4, 5, 2, 6, 7, 3, 1]。