知道后序遍历和中序遍历怎么求前序遍历

### 如何根据后序遍历和中序遍历计算二叉树的前序遍历

通过分析给定的信息可以得知，要从后序遍历和中序遍历的结果推导出二叉树的前序遍历序列。具体过程如下：

#### 后序遍历的特点
在后序遍历中，最后一个访问的是根节点，在此之前先访问左子树再访问右子树[^1]。

#### 中序遍历的特点
对于任意节点而言，如果该节点存在左/右子树，则其左子树中的所有节点都会在这个节点之前被访问到；而它右侧子树内的全部成员则会在之后才遇到。

基于上述特性，可以通过以下逻辑实现从前两种遍历得到第三种——即前序遍历（根->左->右）:

- **确定根节点**：由于后序遍历最后处理的就是当前子树或整个树的根节点，因此可以直接取后序列表最右边的一个元素作为构建新树时的第一个节点也就是最终输出里的第一个位置上的值。

- **划分左右子树范围**
- 利用找到的这个根节点去查找对应的索引于中序数组里；
- 此处左侧部分代表了原树上属于左分支下的所有子孙后代们组成的集合，
右侧剩余的部分自然就是那些位于目标顶点之右侧路径末端所连接着的一切可能存在的下级单位构成的整体了。

- 对这两个新的区间重复执行相同的操作直到不能再分割为止，期间每次都将最新发现出来的“头目”加入到结果集中相应的位置上去形成完整的前序排列形式。

下面是一个Python函数用于完成这一转换工作：

def build_preorder(in_order, post_order):
    if not post_order or not in_order:
        return []

    root_val = post_order[-1]
    preorder_result = [root_val]

    index_of_root_in_inorder = in_order.index(root_val)

    left_subtree_inorder = in_order[:index_of_root_in_inorder]
    right_subtree_inorder = in_order[index_of_root_in_inorder + 1:]

    left_subtree_postorder = post_order[:len(left_subtree_inorder)]
    right_subtree_postorder = post_order[len(left_subtree_inorder):-1]

    # Recursively find the pre-order traversal of subtrees.
    preorder_result += build_preorder(left_subtree_inorder, left_subtree_postorder)
    preorder_result += build_preorder(right_subtree_inorder, right_subtree_postorder)

    return preorder_result

这段代码实现了递归地解析输入参数`in_order`(表示中序遍历) 和 `post_order`(表示后序遍历), 并返回一个按照前序顺序排列的新列表[^2][^3]。