输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给定二叉树的前序和中序遍历，要求重构出原始二叉树。
前序：根、左、右；中序：左、根、右。所以每次把前序数组的第一个元素作为根节点，然后在中序中找到根节点，把中序划分为两半，由此可知道左、右子树子数组的长度，据此把前序也划分为左、右两部分，递归调用。为了快速找到根节点在中序数组中的位置，提前用hash表存储。完整代码如下：
class Solution {
private:
TreeNode* buildTree(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir, unordered_map<int,int> &hash) {
if(pr < pl || ir < il) return NULL;
TreeNode *root = new TreeNode(preorder[pl]);
int im = hash[preorder[pl]];
int len_left = im - il, len_right = ir - im;
root->left = buildTree(preorder, pl + 1, pl + len_left, inorder, il, im - 1, hash);
root->right = buildTree(preorder, pl + len_left + 1, pr, inorder, im + 1, ir, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int,int> hash;
for(int i = 0; i < inorder.size(); ++i) hash[inorder[i]] = i;
int n = preorder.size();
return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, hash);
}
};本代码提交AC，用时32MS。