Java POJ 2255: 二叉树后序遍历的递归解法

POJ 2255 题目是关于利用 Java 编程解决一个二叉树的后序遍历问题。题目要求根据给定的前序遍历（Preorder）和中序遍历（Inorder）序列，重建并输出后序遍历（Postorder）序列。这个问题主要涉及了二叉树的结构理解和递归算法的应用。 首先，理解二叉树的遍历方式是关键。前序遍历的顺序是根节点 -> 左子树 -> 右子树，而中序遍历的顺序是左子树 -> 根节点 -> 右子树。后序遍历则是左子树 -> 右子树 -> 根节点。通过这两个序列，我们可以重构整个二叉树的结构。 解题步骤如下： 1. **读取输入**：使用 `Scanner` 类从标准输入读取前序和中序遍历的字符数组 `pre` 和 `in`。 2. **初始化变量**：定义全局变量 `num` 用于计数，`aftList` 用来存储后序遍历的结果，`pre` 和 `in` 分别表示当前处理的前序和中序序列。 3. **递归函数**：`ExeLeft` 函数接受三个参数：起始索引 `start`，结束索引 `end`，以及当前处理的节点标记 `node`（这里设置为 '0' 表示未访问）。这个函数的主要任务是遍历中序序列找到当前节点的位置，然后利用前序和中序遍历的特性来构建后序遍历。 4. **寻找根节点**：在中序遍历中，找到前序遍历的第一个字符，它就是当前处理的根节点。将这个根节点添加到后序遍历列表 `aftList` 中，并递归处理其左右子树。 5. **递归过程**：对左子树（在中序序列的左侧），调用 `ExeLeft(start, rootIndex - 1, node + 1)`，对右子树（在中序序列的右侧），调用 `ExeLeft(rootIndex + 1, end, node + 1)`，其中 `rootIndex` 是中序遍历中的根节点索引，`node + 1` 表示已访问的节点，因为 `node` 开始时为 '0'，每进入一层递归，`node` 增加 1。 6. **处理边界情况**：当起始索引 `start` 大于结束索引 `end` 时，说明已经遍历完一个完整的子树，递归结束。同时确保 `aftList` 清除多余的元素，只保留实际的后序遍历结果。 7. **输出后序遍历**：遍历 `aftList` 并将元素按照后序遍历的顺序输出，即先输出右子树的根，再输出左子树的根，最后输出当前节点。 8. **错误处理**：注意到代码中有 `runtimeerror` 注释，这可能意味着在某些输入情况下程序会抛出异常。这部分代码可能是为了处理连续输入或者换行符的情况，但在这里略过，因为重点在于算法的描述。 POJ 2255 题目是一个典型的二叉树重构问题，需要对二叉树的遍历有深入理解，并熟练运用递归算法来实现后序遍历。Java 代码实现了这些步骤，通过输入的前序和中序遍历数据，成功地还原了后序遍历的序列。