解题思路

通过二叉树的前序和中序来构建二叉树， 通过规则可以知道，前序的某一位置的值，该值在中序遍历中其左部分为其左孩子的区域，右部分为右孩子的区域，可以一个hashmap 将中序遍历的每个值对应的位置进行保存。不断通过递归来重建二叉树。但有一个难点就是确定遍历的区域范围。难点递归子问题的递归区域范围的确定。

HashMap<Integer,Integer> hashMap=new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
    int preLength=pre.length;
    int inLength=in.length;
    if(preLength!=inLength){
        return null;
    }
    for(int i=0;i<inLength;i++){
        //存储中序遍历中的
        hashMap.put(in[i],i);
    }
    TreeNode head=dfs(pre,in,0,preLength-1,0,inLength-1);
    return head;
}

public TreeNode dfs(int [] pre,int [] in,int pl,int pr,int vl,int vr){
    if(pl>pr){
        return null;
    }
    // 获得当前区域前序遍历第一个元素
    int k = hashMap.get(pre[pl]);
    TreeNode treeNode = new TreeNode(pre[pl]);
    TreeNode left=dfs(pre,in,pl+1,pl+k-vl,vl,k-1);
    TreeNode right=dfs(pre,in,pl+k-vl+1,pr,k+1,vr);
    treeNode.left=left;
    treeNode.right=right;
    return treeNode;
}