105.construct-binary-tree-from-preorder-and-inorder-traversal 从前序与中序遍历序列构造二叉树

原理参照从中序与后序遍历序列构造二叉树，这里直接给出基于vector索引优化之后的版本：

class Solution {
  private:
    TreeNode *get_root(vector<int> &preorder, int pre_l, int pre_r, vector<int> &inorder, int in_l, int in_r) {
        if (pre_l >= pre_r)
            return nullptr;
        TreeNode *root = new TreeNode(preorder[pre_l]);
        int i = in_l;
        while (i < in_r) {
            if (inorder[i] == root->val)
                break;
            i++;
        }
        root->left = get_root(preorder, pre_l + 1, pre_l + 1 + i - in_l, inorder, in_l, i);
        root->right = get_root(preorder, pre_r + i + 1 - in_r, pre_r, inorder, i + 1, in_r);
        return root;
    }

  public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return get_root(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
};