解题思路

这道题要求根据给定的 前序遍历（Preorder） 和 中序遍历（Inorder） 序列，重建二叉树，并输出 后序遍历（Postorder） 结果。

关键观察

1. 前序遍历（Preorder） 的第一个节点是 根节点。
2. 中序遍历（Inorder） 中，根节点将序列分为 左子树 和 右子树。
3. 递归地处理左子树和右子树，直到所有节点都被处理。

步骤

1. 找到根节点：前序遍历的第一个字符即为根节点。
2. 分割中序遍历：
   • 在中序遍历中找到根节点的位置，左侧是左子树的中序遍历，右侧是右子树的中序遍历。
3. 递归构建子树：
   • 左子树的前序遍历长度 = 左子树的中序遍历长度。
   • 右子树的前序遍历长度 = 右子树的中序遍历长度。
4. 后序遍历输出：在递归完成后，按照 左→右→根 的顺序输出节点。

C++ 实现

#include <iostream>
#include <string>
#include <map>
using namespace std;

map<char, int> in_map; // 使用map代替unordered_map

// 递归构建树，并直接输出后序遍历
void buildTree(const string &pre, int pre_start, int pre_end, const string &in, int in_start, int in_end) {
    if (pre_start > pre_end || in_start > in_end) return; // 递归终止条件

    char root_val = pre[pre_start]; // 前序遍历的第一个节点是根
    int root_pos = in_map[root_val]; // 找到根在中序遍历的位置

    int left_size = root_pos - in_start; // 左子树的节点数

    // 递归处理左子树
    buildTree(pre, pre_start + 1, pre_start + left_size, in, in_start, root_pos - 1);

    // 递归处理右子树
    buildTree(pre, pre_start + left_size + 1, pre_end, in, root_pos + 1, in_end);

    cout << root_val; // 后序遍历：最后输出根
}

int main() {
    string preorder, inorder;
    while (cin >> preorder >> inorder) {
        in_map.clear();
        for (int i = 0; i < inorder.size(); ++i) {
            in_map[inorder[i]] = i; // 记录中序遍历字符的位置
        }
        buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
        cout << endl;
    }
    return 0;
}