leetcode 105 c++

LeetCode 105题是关于构建二叉树的问题，题目名称通常是“从前序与中序遍历序列构造二叉树”，这个问题要求根据给定的二叉树的前序遍历序列和中序遍历序列来重建该二叉树。

在C++中，解决这个问题的一种常见方法是使用递归。首先，我们需要理解前序遍历和中序遍历的特点：
1. 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
2. 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

通过这两个序列，我们可以找到根节点的确切位置，然后递归地构建左子树和右子树。具体步骤如下：
1. 在前序遍历中找到根节点（第一个节点）。
2. 在中序遍历中找到根节点的位置，这样就可以确定左子树和右子树的节点个数。
3. 递归地用左子树的前序遍历和中序遍历序列构建左子树。
4. 递归地用右子树的前序遍历和中序遍历序列构建右子树。

下面是一个简化版的C++代码示例，用于解决这个问题：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

private:
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) return nullptr;
        
        TreeNode* root = new TreeNode(preorder[preStart]);
        int inRoot = inStart;
        while (inorder[inRoot] != root->val) inRoot++;
        
        int leftTreeSize = inRoot - inStart;
        
        root->left = build(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, inRoot - 1);
        root->right = build(preorder, preStart + leftTreeSize + 1, preEnd, inorder, inRoot + 1, inEnd);
        
        return root;
    }
};