105. 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

难度中等719
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7

    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return helper(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    public TreeNode helper(int[] preorder, int[] inorder,int pstart,int pend,int start,int end){
        if(pstart>pend){
            return null;
        }// 必须有
        TreeNode root = new TreeNode(preorder[pstart]);
        int idxroot = map.get(preorder[pstart]);
        int leftSize= idxroot - start;//
        root.left = helper(preorder,inorder,pstart+1,pstart+leftSize,start,idxroot-1);
        root.right= helper(preorder,inorder,pstart+leftSize+1,pend,idxroot+1,end);//+1
        return root;
    }