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

题目链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

前序遍历是根在前面，然后是左子树，再是右子树，中序遍历是左子树-根-右子树，通过前序遍历可以找到根，在中序遍历里面确定根的位置后可以知道左子树的长度和右子树的长度，如此可以在前序遍历中找到左子树和右子树的根，如此递归下去

为了更快的找到中序遍历里面根的位置，可以用哈希表存储下来根对应的索引

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);
    }
};