import java.util.HashMap;
import java.util.Map;

public class _106 {
    static class Solution1{
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            //核心思想，后序遍历的数组，最后一个元素一定是 root
            // 通过 root,找到中序遍历的节点位置,它左侧所有元素为左子树，右侧为右子树。
            //通过中序遍历的序列可以计算出左子树和子树的数量。
            //然后通过数量调整后序遍历左右子树在postorder上的位置
            //不断递归重复上述过程
            Map<Integer,Integer> map = new HashMap<>();
            for(int i = 0;i < inorder.length;i++){
                map.put(inorder[i],i);
            }
            return build(map,inorder,postorder,0,inorder.length-1,0,postorder.length-1);

        }
        public TreeNode build(Map<Integer,Integer> map,int[] inorder, int[] postorder,int iL,int iR,int pL,int pR){
            if(iL>iR || pL > pR) return null;
            TreeNode root = new TreeNode(postorder[pR]);
            int i = map.get(root.val);
            int leftCount = i - iL;
            int rightCount = iR - i;
            root.left = build(map,inorder,postorder,iL,i-1,pL,pL+leftCount-1);
            root.right = build(map,inorder,postorder,i+1,iR,pR-rightCount,pR-1);
            return root;
        }

    }
}