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

### 构造二叉树并获取后序遍历

给定前序遍历 `preorder` 和中序遍历 `inorder` 序列可以唯一确定一棵二叉树[^3]。为了获得该二叉树的后序遍历序列，可以通过以下方法：

从前序遍历的第一个元素识别出根节点 A。在中序遍历中定位到这个根节点的位置，发现其位于索引 1 处 (D B G E |A| C H F)，这意味着根节点左侧的部分属于左子树而右侧部分则构成右子树。

对于左子树而言，在前序遍历中的下一个元素即是它的根节点 D；同样地处理右子树的情况，找到对应的根节点 C。继续按照此逻辑递归地解析每一个子树直到所有的节点都被访问过为止。

基于上述分析过程建立起来的二叉树结构如下所示：

        A
       / \
      B   C
     / \   \
    D   E   F
         /
        G   

最后执行一次完整的后序遍历操作来收集最终的结果列表 DGEBHFCA。

因此，根据所给定的前序遍历 ABDEGCFH 及中序遍历 DBGEACHF 所构造出来的二叉树之后的遍历顺序应为：DGEBHFCA[^2]。

相关问题

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

已知前序遍历序列为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]。