//测试

 public class BuildTreeUsingInorderAndPostorder {

      public static void main(String[] args) {

             int[] postSort={7,4,2,5,8,6,3,1};

             int[] inSort={4,7,2,1,5,3,8,6};

             System.out.println(new Solution2().buildTree(postSort, inSort));

         }

 }

 //利用中序和后序重建二叉树

 class Solution2 {

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

         //参数校验

         if(postorder==null||inorder==null||postorder.length!=inorder.length||postorder.length==0)

             return null;

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

     }

     /**

      * 构建二叉树，数据输入的正确性由输入数据自己保证

      *

      * @param postorder                    后序遍历的结果

      * @param startPostorder  后序遍历的开始位置

      * @param endPostorder    后序遍历的结束位置

      * @param inorder        中序遍历的结果

      * @param startInorder   中序遍历的开始位置

      * @param endInorder     中序遍历的结束位置

      * @return 二叉树的根结点

      */

     private TreeNode buildTreeCore(int[] inorder,int startInorder, int endInorder,

             int[] postorder, int startPostorder, int endPostorder) {

         // 只有一个元素时直接返回该节点，这也是递归结束的出口标志

         if(startPostorder==endPostorder){

             return new TreeNode(postorder[endPostorder]);

         }else{

             // 记录根结点的在中序遍历中的位置

             int rootIn=startInorder;

             for(int i=startInorder;i<=endInorder;i++){

                 if(inorder[i]==postorder[endPostorder]){

                     rootIn=i;

                     break;

                 }

             }

             // 创建根结点

             TreeNode root=new TreeNode(inorder[rootIn]);

              // 左子树的结点个数

             int leftLength=rootIn-startInorder;

             if(leftLength>0){

                 // startPostorder, startPostorder+leftLength-1：左子树在后序序列中的起始和结束位置

                 root.left=buildTreeCore(inorder, startInorder, rootIn-1, postorder, startPostorder, startPostorder+leftLength-1);

             }

             // 右子树的结点个数

             int rightLength=endInorder-rootIn;

             if(rightLength>0){

                 // startPostorder+leftLength, endPostorder：左子树在后序序列中的起始和结束位置

                 root.right=buildTreeCore(inorder, rootIn+1, endInorder, postorder, startPostorder+leftLength, endPostorder-1);

             }

             return root;

         }

     }

 }

 //二叉树节点定义

 class TreeNode {

      int val;

      TreeNode left;

      TreeNode right;

      TreeNode(int x) { val = x; }

 }