c++给出先序遍历中序遍历构造出二叉树

在C++中，利用先序遍历（Preorder Traversal）和中序遍历（Inorder Traversal）构建二叉树通常涉及到递归的过程。这两个序列对于每个节点来说都是关键信息：

1. 先序遍历：根节点 -> 左子树 -> 右子树
- 它包含的信息足够确定一个节点的位置：第一项就是根节点。

2. 中序遍历：左子树 -> 根节点 -> 右子树
- 对于已知的根节点，中序遍历可以用来找到它的左、右子树。

下面是构造过程的基本步骤：

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 root_val = preorder[0];
    auto root = new TreeNode(root_val);

    // 找到根值在中序遍历中的位置
    size_t root_index = search_inorder(inorder, root_val);

    // 使用中序遍历找到左子树和右子树
    root->left = buildTree(preorder.begin() + 1, inorder.begin() + root_index);
    root->right = buildTree(preorder.begin() + root_index + 1, inorder.end());

    return root;
}

// 辅助函数，在中序遍历中查找指定值的位置
size_t search_inorder(vector<int>& inorder, int target) {
    for (size_t i = 0; i < inorder.size(); ++i) {
        if (inorder[i] == target) return i;
    }
    return inorder.size();
}