题解 | #重建二叉树#

观察前序遍历和中序遍历数组可以发现：前序的第一个元素可以把中序分成左右两个部分，那么中序的右边部分就是右子树，左边部分就是左子树。递归进行建造即可。

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0){
            return nullptr;
        }
        TreeNode * root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.size(); ++i){
            if(vin[i] == root->val){
                root->left = reConstructBinaryTree(copy_vec(pre, 1, i + 1), copy_vec(vin, 0, i));
                root->right = reConstructBinaryTree(copy_vec(pre, i + 1, pre.size()), copy_vec(vin, i + 1, vin.size()));
            }
        }
        return root;
    }
    vector<int> copy_vec(vector<int> vec, int start, int end){
        vector<int> res;
        for(int i = start; i < end; ++i){
            res.push_back(vec[i]);
        }
        return res;
    }
};