用C++实现：已知中根序列和后根序列求先根序列

在C++中，给定一棵二叉树的中序遍历（中根序列）和后序遍历（后根序列），我们可以利用这两个序列重构出先序遍历（先根序列）。因为对于任何二叉树，其先序遍历、中序遍历和后序遍历有固定的对应规则：

- 先序遍历（根节点 -> 左子树 -> 右子树）
- 中序遍历（左子树 -> 根节点 -> 右子树）
- 后序遍历（左子树 -> 右子树 -> 根节点）

后根序列实际上就是先将整个序列翻转得到的，因此后根序列是右子节点 -> 左子节点 -> 根节点。

以下是一个简单的步骤来重建先根序列：

1. 确认两个序列长度相等，并假设它们都是有效的二叉树遍历结果。
2. 创建一个空栈和一个临时变量用于存储当前处理的节点，初始化为后根序列的第一个元素。
3. 遍历后根序列，遇到根节点时：
a. 将该节点入栈。
b. 检查中序序列的下一个元素是否是该节点，如果是，则表示已经处理完左子树，将栈顶元素弹出并加入先根序列；如果不是，则继续处理右子树，跳到后根序列的下一个节点。
4. 当后根序列遍历完毕，栈中剩下的元素即为根节点，依次出栈并加入先根序列。

#include <vector>
#include <stack>

std::vector<int> buildPreorder(const std::vector<int>& inorder, const std::vector<int>& postorder) {
    int in_index = 0;
    std::stack<int> stack;

    for (int &node : postorder) {
        if (inorder[in_index] == node) {
            stack.push(node);
            while (!stack.empty() && inorder[in_index + 1] != stack.top()) {
                in_index++;
                node = stack.top();
                stack.pop();
            }
            in_index++;
        }
    }

    std::vector<int> preorder;
    while (!stack.empty()) {
        preorder.push_back(stack.top());
        stack.pop();
    }

    return preorder;
}