/**
 * 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 {
    int postOrderEndPosition ;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postOrderEndPosition = postorder.length-1;
        return makeTree(inorder, postorder, 0, inorder.length-1);
    }
    public TreeNode makeTree(int []in, int []post, int low, int high){
        if( low <= high ){
            
            int pos = returnRootPosition(in, post, low, high);
            TreeNode root = new TreeNode( in[pos] );
            root.right =  makeTree(in,post, pos+1, high);
            root.left =  makeTree(in,post, low, pos-1);
            return root;
        }
        return null;
    }
    
    int returnRootPosition(int []in, int []post, int low, int high ){
    
        if( low == high){
            return low;
        }
        if(low < high){
            for(int k = postOrderEndPosition; k >= 0; k--){
                for(int i = low; i<=high; i++){
                    if( post[k] == in[i]){
                        postOrderEndPosition--;
                        return i;
                    }
                }
            }            
        }
        return -1;
    }
}
/*
和105. (Preorder and Inorder)不同的点是要找到root
postorder -> L, Right, Root
inorder   -> L, Root, Right
froot: 在postorder中找到第一个在inorder倒序遍历时出现的元素，就是当前点元素
            build([9, 15, 7, 20, (3)], [9, (3), 15, 20, 7])
            root=3
            /                           \
           /                             \
    build([9])                    build([15, 20, 7])
    foort()=9                           froot()=20
                                      /           \
                                     /             \
                                build([15])     build([7])
                                root=15         root=15
*/