输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
主要利用二叉树前序，中序遍历的性质 | 递归
前序数组的首元素是当前根节点，中序数组中以根节点为界划分为两部分，左边是左子树，右边是右子树。如下图，我们可以找到左子树和右子树的前序、中序数组，然后再以同样的方法构建左右子树。
所以关键的步骤为每层递归的处理过程：通过前序数组、中序数组划分左子树和右子树的前序、中序数组，划分方法是前序数组第一个元素为root，在中序数组中找到root对应位置，左边作为左子树中序数组，右边作为右子树中序数组，而左右子树前序数组为根据左子树元素个数、右子树元素个数瓜分前序数组。
class Solution {
public:
map hash;
vector preorder, inorder;
TreeNode* buildTree(vector& _preorder, vector& _inorder) {
//if (_preorder.empty() || _inorder.empty()) return NULL;
preorder = _preorder, inorder = _inorder;
for (int i = 0; i < inorder.size(); i++) hash[inorder[i]] = i; //技巧，快速找到元素位置
return dfs(0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* dfs(int pl, int pr, int il, int ir) {
if (pl > pr) return nullptr;
auto root = new TreeNode(preorder[pl]); //前序数组首元素是当前root
int k = hash[root->val]; //找到root在中序数组中的位置
TreeNode* left = dfs(pl + 1, pl + k - il, il, k - 1);
TreeNode* right = dfs(pl + k - il + 1, pr, k + 1, ir);
root->left = left, root->right = right;
//cout<val<<" ";
return root;
}
};
