已知前序遍历和中序遍历求后序遍历

已知前序遍历序列为A-B-D-E-G-C-F，中序遍历序列为D-B-G-E-A-C-F，我们可以通过递归的方式来求解后序遍历序列。

首先，我们可以观察到前序遍历序列的第一个元素A就是整个树的根节点。然后，在中序遍历序列中找到根节点A的位置，将中序遍历序列分为左子树和右子树两部分。

对于左子树，它的前序遍历序列为B-D-E-G，中序遍历序列为D-B-G-E。同样地，对于右子树，它的前序遍历序列为C-F，中序遍历序列为C-F。

接下来，我们可以递归地对左子树和右子树进行求解。最后，将根节点A放在后序遍历序列的最后。

根据上述步骤，我们可以得到后序遍历序列为D-G-E-B-F-C-A。

相关问题

已知前序遍历和中序遍历，求后序遍历

已知一棵二叉树的前序遍历和中序遍历，可以通过以下步骤求出后序遍历：

1. 找到前序遍历的第一个节点，即根节点。
2. 在中序遍历中找到根节点，从而确定左子树和右子树的范围。
3. 根据左子树和右子树的范围，可以在前序遍历中确定左子树和右子树的前序遍历。
4. 对左子树和右子树分别递归进行上述步骤，直到叶子节点。
5. 最后将左子树的后序遍历、右子树的后序遍历以及根节点合并起来就是整棵树的后序遍历。

下面是一个示例：

已知前序遍历为：[1, 2, 4, 5, 3, 6, 7]
已知中序遍历为：[4, 2, 5, 1, 6, 3, 7]

首先找到前序遍历的第一个节点，即1，它是整棵树的根节点。
在中序遍历中找到1，从而确定左子树的范围为[4, 2, 5]，右子树的范围为[6, 3, 7]。
根据左子树和右子树的范围，在前序遍历中可以确定左子树的前序遍历为[2, 4, 5]，右子树的前序遍历为[3, 6, 7]。
对左子树和右子树分别递归进行上述步骤，最终得到左子树的后序遍历为[4, 5, 2]，右子树的后序遍历为[6, 7, 3]。
最后将左子树的后序遍历、右子树的后序遍历以及根节点1合并起来就是整棵树的后序遍历：[4, 5, 2, 6, 7, 3, 1]。

已知前序遍历和后序遍历如何推倒中序遍历

根据前序遍历和后序遍历无法直接推导出唯一的中序遍历。因为前序遍历只能确定根节点的位置，而后序遍历只能确定叶子节点的位置。而中序遍历是根据左子树先被遍历，然后是根节点，最后是右子树的规则进行遍历的。这种情况下，无法直接通过前序和后序遍历确定每个节点的左右子树的相对位置关系。因此，无法准确地推导出中序遍历。