从前序与中序遍历序列构造二叉树

题目链接：从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        int mid = 0;
        while (mid < inorder.size() && inorder[mid] != preorder[0]) {
            mid++;
        }

        vector<int> leftIn(inorder.begin(), inorder.begin() + mid);
        vector<int> rightIn(inorder.begin() + mid + 1, inorder.end());

        vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + mid);
        vector<int> rightPre(preorder.begin() + 1 + mid, preorder.end());

        root->left = buildTree(leftPre,leftIn);
        root->right = buildTree(rightPre,rightIn);
        return root;
    }
};