利用c++实现由后序、中序序列构造二叉树的代码

在C++中，我们可以利用递归的方式从二叉搜索树的中序遍历（In-order traversal）和后序遍历（Post-order traversal）序列重构出原始的二叉树。这里是一个简单的示例代码：

#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 根据后序遍历和中序遍历重建二叉树
TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder) {
    if (postorder.empty() || inorder.empty()) return NULL; // 如果遍历序列为空，则返回空指针

    // 通过后序遍历找到根节点，并将其值存入root
    int root_val = postorder.back();
    TreeNode* root = new TreeNode(root_val);
    postorder.pop_back(); // 移除后序遍历中的根节点

    // 中序遍历找到左子树和右子树的位置
    size_t index = find(inorder.begin(), inorder.end(), root_val); // 找到根节点在inorder中的位置
    vector<int> left_inorder(inorder.begin(), index);
    vector<int> right_inorder(index + 1, inorder.end());

    // 递归构建左子树和右子树
    root->left = buildTree(postorder, left_inorder);
    root->right = buildTree(postorder, right_inorder);

    return root;
}

// 测试函数
void printInOrder(TreeNode* node) {
    if (node == nullptr) return;
    printInOrder(node->left);
    cout << node->val << " ";
    printInOrder(node->right);
}

int main() {
    vector<int> postorder = {4, 8, 2, 5, 1, 6, 3, 7};
    vector<int> inorder = {9, 3, 4, 1, 6, 2, 5, 7, 8};
    
    TreeNode* root = buildTree(postorder, inorder);
    cout << "Original tree in In-order: ";
    printInOrder(root);
    cout << endl;

    return 0;
}

这段代码首先找到后序遍历序列中的最后一个元素作为根节点，然后在中序遍历中找出这个元素的位置，划分出左右子树的中序序列。接着递归地对左右子树进行同样的操作，直到所有节点都被创建并连接起来。