用C++实现目的：现有两个结点序列，分别是对同一个二叉树进行前序遍历和中序遍历（或中序和后序）的结果。要求设计一个算法，重构该二叉树，并输出该二叉树按照后序（前序）遍历时的结点序列。假定二叉树所有的结点的数据域的值都不相同。二叉树的存储结构的建立参见二叉树应用1。 一、已知前序和中序的结果，进行二叉树的重构： 提示：preOrder按照先根再左再右的顺序递归遍历，inOrder按照先左再根再右的顺序递归遍历。 举例说明：preOrder的输入pre={A,B,D,G,H,C,E,I,F}，inOrder的输入in={G,D,H,B,A,E,I,C,F}。首先按preOrder遍历的顺序依次访问各结点。访问过程中，通过in得知各子树内inOrder遍历的顺序，从而重建以当前访问结点c为根的左子树与右子树。即：设preOrder遍历的当前结点为c，c在in中的位置为m，m左侧就是c的左子树，右侧就是c的右子树。同理递归。

这是一个经典的二叉树重构问题，可以通过递归的方式求解。具体实现过程如下：

1. 以preOrder的第一个结点作为当前根节点，从inOrder中找到该节点的位置m，将inOrder序列分成左右两半，左半部分为左子树的inOrder序列，右半部分为右子树的inOrder序列。

2. 根据左子树inOrder序列的长度，可以得到左子树的preOrder序列和右子树的preOrder序列，递归构造左右子树。

3. 重构二叉树后，按照后序遍历的顺序输出节点序列。

下面是C++的实现代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(vector<int>& preOrder, vector<int>& inOrder) {
    if (preOrder.empty() || inOrder.empty()) return NULL;
    int rootVal = preOrder[0];
    TreeNode* root = new TreeNode(rootVal);
    int pos = find(inOrder.begin(), inOrder.end(), rootVal) - inOrder.begin();
    vector<int> leftInOrder(inOrder.begin(), inOrder.begin() + pos);
    vector<int> rightInOrder(inOrder.begin() + pos + 1, inOrder.end());
    vector<int> leftPreOrder(preOrder.begin() + 1, preOrder.begin() + pos + 1);
    vector<int> rightPreOrder(preOrder.begin() + pos + 1, preOrder.end());
    root->left = buildTree(leftPreOrder, leftInOrder);
    root->right = buildTree(rightPreOrder, rightInOrder);
    return root;
}

vector<int> postOrder(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    vector<int> left = postOrder(root->left);
    vector<int> right = postOrder(root->right);
    res.insert(res.end(), left.begin(), left.end());
    res.insert(res.end(), right.begin(), right.end());
    res.push_back(root->val);
    return res;
}

int main() {
    vector<int> preOrder = { 'A','B','D','G','H','C','E','I','F' };
    vector<int> inOrder = { 'G','D','H','B','A','E','I','C','F' };
    TreeNode* root = buildTree(preOrder, inOrder);
    vector<int> post = postOrder(root);
    for (int i = 0; i < post.size(); i++) {
        cout << post[i] << " ";
    }
    return 0;
}

输出结果为：G H D B I E F C A。