/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if(inorder==null&&postorder==null||(inorder.length==0&&postorder.length==0)) return null;

        return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);

    }

    public TreeNode build(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart,int postEnd){

        if(inStart>inEnd||postStart>postStart) return null;

        TreeNode root=new TreeNode(postorder[postEnd]); //后续遍历的最后一个是根节点

        //在中序遍历中找到根节点的位置

        int i;

        for( i=inStart;i<=inEnd;i++){

            if(inorder[i]==postorder[postEnd]) break;

        }

        root.left=build(inorder,inStart,i-1,postorder,postStart,postStart+i-inStart-1);

        root.right=build(inorder,i+1,inEnd,postorder,postStart+i-inStart,postEnd-1);

        return root;

    }

}