Description 小Valentine非常喜欢玩二叉树，她喜欢的游戏是随意构造一颗二叉树，用大写字母编号标识结点。下图是她构造的二叉树中的一棵： D / \ B E / \ \ A C G / F 为了向她的后代记录她所创建的树，她给每棵树写下两串字符串，表示后序遍历（左子树，右子树，根）和中序遍历（左子树，根，右子树）的结果。 对于上面的树，后序遍历的结果是ACBFGED，中序遍历的结果是ABCDEFG。 她认为这样的一对字符串给出了重构这棵树的足够的信息（但她从来没有尝试去重构二叉树）。 过了好些年，她认识到重构这些树的确是可能的。对于同一棵树，同一个字母不会用两次。 然而，如果手工完成重构二叉树，那是非常乏味的。因此，请您编写一个程序来为她完成这一项工作。 Input 输入包含一个或多个测试用例。每个测试用例一行，给出两个字符串，表示对二叉树进行后序遍历和中序遍历的结果。这两个字符串都是由大写字母组成（因此它们的长度不超过26）。 Output 将每个测试用例转化为Valentine的二叉树，并在一行中输出树的先序遍历（根，左子树，右子树）的结果。 Sample Input ACBFGED ABCDEFG CDAB CBAD Sample Output DBACEGF BCAD 写一份c++代码

当然，下面是相同的问题的C++代码实现：

#include <iostream>
#include <unordered_map>
using namespace std;

struct Node {
    char value;
    Node* left;
    Node* right;

    Node(char val) : value(val), left(nullptr), right(nullptr) {}
};

Node* buildTree(const string& postorder, const string& inorder, int post_start, int post_end, int in_start, int in_end, unordered_map<char, int>& in_map) {
    if (post_start > post_end || in_start > in_end) {
        return nullptr;
    }

    char root_value = postorder[post_end];
    Node* root = new Node(root_value);

    int root_index = in_map[root_value];

    int left_tree_size = root_index - in_start;

    root->left = buildTree(postorder, inorder, post_start, post_start + left_tree_size - 1, in_start, root_index - 1, in_map);
    root->right = buildTree(postorder, inorder, post_start + left_tree_size, post_end - 1, root_index + 1, in_end, in_map);

    return root;
}

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }

    cout << root->value;
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

void constructTree(const string& postorder, const string& inorder) {
    unordered_map<char, int> in_map;
    for (int i = 0; i < inorder.length(); ++i) {
        in_map[inorder[i]] = i;
    }

    Node* root = buildTree(postorder, inorder, 0, postorder.length() - 1, 0, inorder.length() - 1, in_map);

    preorderTraversal(root);
    cout << endl;

    // 清理内存
    // ...
}

int main() {
    string postorder, inorder;
    while (cin >> postorder >> inorder) {
        constructTree(postorder, inorder);
    }
    return 0;
}

这段代码使用递归的方式实现了二叉树的构建和先序遍历。它首先构建了一个哈希表，用于快速查找中序遍历中节点的索引。然后，通过调用 `buildTree` 函数来递归构建二叉树，并通过 `preorderTraversal` 函数进行先序遍历。

希望对你有帮助！如果你还有其他问题，请随时问。