输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
输入: 前序遍历数组preorder = [3,9,20,15,7], 中序遍历数组inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
解题思路：前序遍历数组=[根节点，[左子树]，[右子树]]，中序遍历数组=[[左子树]，根节点，[右子树]]。
根节点root为前序数组的第一个节点值，找到这个root在中序数组中的位置，其中左边为左子树，右边为右子树。
对此可使用递归操作，求得root的左右节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> hashTable = new HashMap<Integer, Integer>();//定义一个map存储中序遍历数组的值下标，key为值，value为值对应的下标，可快速定位到key值对应的下标。
for(int i=0; i<inorder.length; i++) {
hashTable.put(inorder[i], i);//初始化 map
}
return dfs(hashTable, preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
}
public TreeNode dfs(Map<Integer, Integer> hashTable, int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
// preorderLeft表示前序数组的对应的子数组的左下标；
// preorderRight 表示前序数组的对应的子数组的右下标；
// inorderLeft t表示中序数组的对应的子数组的左下标；
// inorderRight 表示中序数组的对应的子数组的右下标；
if(preorderLeft>preorderRight) {
return null;
}
TreeNode root = new TreeNode(preorder[preorderLeft]); // 根节点root为前序数组的第一个节点值
int rootIndex = hashTable.get(root.val); // 从map中找到这个root在中序数组中的位置
int leftTreeSize = rootIndex - inorderLeft; // 左子树长度 = root 在中序数组中的位置-中序数组的首下标
//root的左节点=dfs（左子树）
root.left = dfs(hashTable, preorder, inorder, preorderLeft+1, preorderLeft+leftTreeSize, inorderLeft, rootIndex-1);
//root的左节点=dfs（右子树）
root.right = dfs(hashTable, preorder, inorder, preorderLeft+1+leftTreeSize, preorderRight, rootIndex+1, inorderRight);
return root;
}
}
