使用前序和中序遍历求POJ 2255题后序遍历算法

本题是POJ 2255的一个编程问题，要求根据给定的前序遍历（preorder）和中序遍历（inorder）序列，推导出后续遍历（postorder）序列。在计算机科学中，二叉树的遍历方式有三种：前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。这个问题的核心在于利用前序和中序遍历的特点来重构后序遍历。 首先，让我们了解这些遍历方法的工作原理： 1. 前序遍历：访问根节点，然后遍历左子树，最后遍历右子树。 2. 中序遍历：遍历左子树，访问根节点，最后遍历右子树。 3. 后序遍历：遍历左子树，遍历右子树，最后访问根节点。 给定的C++代码实现了一个名为`travel`的递归函数，该函数接收四个参数： - `pStart` 和 `pEnd`：表示前序遍历中的当前范围，即根节点及其子树。 - `inStart` 和 `inEnd`：表示中序遍历中的当前范围。 函数的逻辑如下： - 如果`pStart`大于`pEnd`，说明已经到达叶子节点，直接将当前前序节点添加到后序结果数组`postorder`的末尾，并返回。 - 找到前序遍历中当前根节点在中序遍历中的位置`i`，这个位置对应于后序遍历中该节点的左右子树的分界点。 - 分别对左子树（`pStart + i - inStart + 1`到`pEnd`）和右子树（`pStart + 1`到`pStart + i - inStart`）进行递归调用`travel`，先处理左子树，再处理右子树，这是后序遍历的原则。 `main`函数部分： - 读取输入的前序和中序遍历序列，存储长度并初始化后序遍历数组。 - 调用`travel`函数，从根节点开始遍历整个树，得到完整的后序遍历结果。 - 输出结果到控制台。 总结来说，此题的关键在于理解二叉树的遍历逻辑，尤其是后序遍历与前序、中序遍历之间的关系。通过递归调用和区间划分，代码实现了根据前序和中序遍历重建后序遍历的过程。在实际编程中，这种技术对于处理二叉树的构建和搜索问题非常有用。