用C语言根据二叉树的前中序建立二叉树

在C语言中，根据二叉树的前序遍历和中序遍历重建一棵二叉树是一个常见的算法问题。这里我们将简述一种常用的递归方法：

假设你已经有了两个函数，分别用于处理前序遍历（preorder）和中序遍历（inorder）。前序遍历通常的第一个元素是根节点，然后是左子树，最后是右子树；而中序遍历的顺序则是左子树、根节点、右子树。

1. 前序遍历（Preorder）函数，`int preorder[ ]` 和 `int pre_size`：
- 这是根节点的索引
- 返回当前访问到的最后一个元素的下标

2. 中序遍历（Inorder）函数，`int inorder[ ]` 和 `int in_size`：
- 返回已排序数组的末尾元素索引

你可以使用以下步骤重构树结构：

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

// 根据前序遍历和中序遍历重建二叉树
struct TreeNode* buildTree(int preorder[], int preorderSize, int inorder[], int inorderSize) {
    if (preorderSize == 0) return NULL;

    // 找到前序遍历中的根节点值在中序遍历中的位置
    int rootIndex = searchInOrder(inorder, inorderSize, preorder[0]);

    // 创建新的根节点
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = preorder[0];

    // 使用中序遍历分割点创建左右子树
    root->left = buildTree(preorder + 1, preorderSize - 1, inorder, rootIndex);
    root->right = buildTree(preorder + 1, preorderSize - 1, inorder + rootIndex + 1, inorderSize);

    return root;
}

// 辅助函数，在中序遍历中查找特定值的位置
int searchInOrder(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) return i;
    }
    return size; // 如果没找到目标，返回数组末尾
}