【LeetCode热题100】【二叉树】从前序与中序遍历序列构造二叉树

class Solution {
public:
    unordered_map<int, int> index;
    vector<int> preorder, inorder;

    TreeNode *build(int pre_left, int pre_right, int in_left, int in_right) {
        if (pre_left > pre_right)
            return nullptr;
        TreeNode *root = new TreeNode(preorder[pre_left]);
        int in_root = index[preorder[pre_left]];
        int left_size = in_root - in_left;
        root->left = build(pre_left + 1, pre_left + left_size, in_left, in_root - 1);
        root->right = build(pre_left + left_size + 1, pre_right, in_root + 1, in_root);
        return root;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        this->preorder = preorder;
        this->inorder = inorder;
        for (int i = 0; i < inorder.size(); i++)
            index[inorder[i]] = i;
        return build(0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};