力扣-889-根据前序和后序遍历构造二叉树

HashMap<Integer,Integer> map;//记录结点值在后序中的下标
public TreeNode constructFromPrePost(int[] pre, int[] post) {
    if(pre == null || post == null
        || pre.length <= 0 || post.length <= 0
        || pre.length != post.length)   return null;
        map = new HashMap<>();
        for(int i = 0;i<post.length;i++){
            map.put(post[i],i);
        }

    return construct(0,pre.length-1,pre,0,post.length-1,post);
}

private TreeNode construct(int prel,int prer,int[] pre,int postl,int postr,int[] post){
    if(prel > prer) return null;
    if(prel == prer)    return new TreeNode(pre[prel]);

    TreeNode root = new TreeNode(pre[prel]);
    if(prel < prer){//还有子节点
        int leftval = pre[prel+1];//默认一定有左子树，左子树根节点下标就是prel+1
        int leftcount = map.get(leftval) - postl + 1; //计算左子树个数
        root.left = construct(prel+1,prel+leftcount,pre,postl,postr,post);
        root.right = construct(prel+leftcount+1,prer,pre,postl+leftcount,postr,post);
    }
    return root;
}