/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

// 解法一： 很好理解但太慢了
// class Solution {
//     public TreeNode buildTree(int[] inorder, int[] postorder) {
//         if(postorder.length==0){
//             return null;
//         }
//         TreeNode root = new TreeNode(postorder[postorder.length-1]);
//         if(postorder.length==1){
//             return root;
//         }
//         // 寻找切割点
//         int idx;
//         for(idx = 0; idx<inorder.length; idx++){
//             if(inorder[idx] == root.val){
//                 break;
//             }
//         }
//         // 递归子数组
//         root.left = buildTree(Arrays.copyOfRange(inorder,0,idx), Arrays.copyOfRange(postorder,0,idx));
//         root.right = buildTree(Arrays.copyOfRange(inorder,idx+1,inorder.length), Arrays.copyOfRange(postorder,idx,postorder.length-1));

//         return root;
//     }
// } 

// 解法二
class Solution {
    Map<Integer,Integer> map; // 转换inorder，更快查找切割点索引
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i = 0; i<inorder.length; i++){
            map.put(inorder[i],i);
        }
        return recur(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    // 参数：中序数组-处理起点-处理终点，三者确定新的中序数组，，，后序同理
    private TreeNode recur(int[] inorder, int inStart, int inEnd, int[] postorder, int poStart, int poEnd){
        // 终止条件
        if (inStart == inEnd || poStart == poEnd) {// 相等了就到叶子了
            return null;
        }
        // 递归逻辑
        int rootVal = postorder[poEnd-1];
        TreeNode root = new TreeNode(rootVal);
        int rootIdx = map.get(rootVal);
        root.left = recur(inorder, inStart, rootIdx, postorder, poStart, poStart+rootIdx-inStart);
        root.right = recur(inorder, rootIdx+1, inEnd, postorder, poStart+rootIdx-inStart, poEnd-1);

        return root;
    }
}