C语言实现：已知二叉树的后根序列和中根序列，创建一棵二叉树

在C语言中，给定一个二叉树的后序遍历（Postorder Traversal）序列和中序遍历（Inorder Traversal）序列，我们可以重建这棵树。这是因为后序遍历的顺序是左->右->根，而中序遍历的顺序是左->根->右，这两个序列包含了所有节点的信息。

以下是创建二叉树的一种常见方法：

1. 首先，我们需要两个函数分别用于计算后序遍历到中序遍历的转换点（即根节点的位置）和后序遍历中的最后一个元素（表示右子树）。
- 后序遍历到中序遍历转换点：对于后序遍历，找到倒数第二个元素就是根，因为它在后序遍历中位于右子树之前。
- 后续遍历最后一个元素：由于后序遍历的顺序是左->右->根，所以最后一个元素对应的节点是右子树的最右节点。

2. 然后，我们可以在main函数中按照如下步骤构造二叉树：
- 初始化两个栈，一个用于存储后序遍历结果，另一个用于辅助恢复过程。
- 对于后序遍历序列，首先入栈后序遍历的最后一个元素（右子树），然后找到中序遍历中的对应位置，将该位置前的所有节点依次出栈并插入到当前位置，最后将剩余的元素作为新节点的左子树添加。

示例代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* buildTree(int* post, int* inOrder, int n) {
    if (n == 0) return NULL;
    
    // 找到后序遍历到中序遍历的转换点
    int postIndex = n - 2; // 假设有三个元素，最右边的是右子树
    int rootVal = post[postIndex]; // 根节点值
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = rootVal;

    // 在中序遍历中找到根节点，它分隔了左右两部分
    for (int i = 0; inOrder[i] != rootVal; ++i) {}

    // 将根节点及其右子树构建出来
    root->left = buildTree(post + 1, inOrder, i); // 左子树
    root->right = buildTree(post + i + 1, inOrder + i + 1, n - i - 2); // 右子树

    return root;
}

// ... 其他辅助函数 ...

int main() {
    // 假设后序遍历和中序遍历分别为 post[] 和 inOrder[]
    int n = sizeof(post) / sizeof(post[0]);
    TreeNode* root = buildTree(post, inOrder, n);
    // 现在可以对root进行操作，比如打印其结构等
    // ...
    return 0;
}