用C++实现先序加中序构建二叉树

在C++中，我们可以使用递归的方式来实现从先序遍历和中序遍历构建二叉树。二叉搜索树通常有如下的性质：根节点值大于其左子树中所有节点的值，并小于其右子树中所有节点的值。以下是基本的步骤：

**先序遍历（Preorder）：** 首先访问根节点，然后遍历左子树，最后遍历右子树。
**中序遍历（Inorder）：** 先遍历左子树，然后访问根节点，最后遍历右子树。

下面是构建函数的基本框架：

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 nullptr;

    // 先序的第一个元素是当前根节点
    TreeNode* root = new TreeNode(preorder[0]);

    // 找到中序中对应根节点的位置
    int inRootIndex = find(inorder.begin(), inorder.end(), preorder[0]);

    // 使用中序的前半部分构建左子树，后半部分构建右子树
    root->left = buildTree(vector<inorder>{inorder.begin(), inRootIndex}, inorder.begin(), inRootIndex);
    root->right = buildTree(vector<inorder>{inRootIndex + 1}, inorder.end(), inorder.end());

    return root;
}

// 辅助函数，查找给定值在有序数组中的索引
size_t find(vector<int>::iterator start, vector<int>::iterator end, int target) {
    auto it = std::find(start, end, target);
    if (it == end) throw runtime_error("Element not found");
    return it - start;
}

在这个函数里，我们首先检查输入是否为空，然后找到先序遍历中的根节点，接着在中序遍历中定位这个根节点的位置，然后递归地对左右子树进行同样的操作。`find`辅助函数用于在中序序列中找到目标值的位置。