已知二叉树的前序和中序序列，编写算法建立该二叉树如何用c++构建

在C++中，给定二叉树的前序遍历（根节点->左子树->右子树）和中序遍历（左子树->根节点->右子树），可以利用这两个顺序的信息重建整个二叉树。这是因为前序遍历的第一个元素是根节点，而中序遍历可以帮助我们找到根节点的位置。

下面是一个简单的步骤描述和示例代码：

1. 首先定义两个辅助函数：一个用于查找根节点在中序遍历中的位置，另一个用于递归构建子树。

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

int findRootIndex(vector<int>& inorder, int target) {
    // 中序遍历找到目标值的位置
    // 注意索引从0开始，所以减一
    return lower_bound(inorder.begin(), inorder.end(), target) - inorder.begin();
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return nullptr;
    }
    
    // 获取根节点值
    int rootVal = preorder[0];
    int rootIndex = findRootIndex(inorder, rootVal);

    // 构建当前根节点
    TreeNode* root = new TreeNode(rootVal);

    // 使用中序遍历来递归构建左右子树
    root->left = buildTree(preorder.begin() + 1, inorder.begin() + rootIndex);
    root->right = buildTree(preorder.begin() + rootIndex + 1, inorder.end());

    return root;
}

2. 最后，调用`buildTree`函数，传入前序遍历和中序遍历数组作为参数，返回根节点指针，即构建完成的二叉树。

vector<int> preOrder = {1, 2, 3};
vector<int> inOrder = {2, 1, 3};
TreeNode* tree = buildTree(preOrder, inOrder);