package com.exe5.offer;

/**

 * 21【题目】输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

 *             如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

 *    【注】二叉搜索树特点：左子树比根结点值小，右子树比根结点值大。

 *    【思路】①根据后序遍历结果确定根结点；

 *             ②判断所有左子树是否比根结点值小；

 *             ③判断所有右子树是否比根结点值大；

 *           ④使用递归，继续分别判断左右子树中是否符合这一特点。

 * @author WGS

 *

 */

public class VerifySequenceOfBST {

    public boolean verifySequenceOfBST(int[] arrOfPostOrder){

        if(arrOfPostOrder==null) return false;

        int len=arrOfPostOrder.length;//

        System.out.println("len:"+len);//

        int rootVal=arrOfPostOrder[len-1];//根据后序遍历结果得到根结点值

        //判断左子树(<根结点值)

        int i=0;

        for(;i<len-1;i++){//

            if(arrOfPostOrder[i]>rootVal)

                 break;

        }

        System.out.println(i);//3

        //判断右子树（>根结点值）

        for(int j=i;j<len-1;j++){

            if(arrOfPostOrder[j]<rootVal)

                 return false;

        }

        //继续判断左子树

        int[] leftTree=new int[(len-1)/2];//

        System.arraycopy(arrOfPostOrder, 0, leftTree, 0, (len-1)/2);

        boolean leftFlag=true;

        if(i>0){

            leftFlag=verifySequenceOfBST(leftTree);

        }

        //继续判断右子树

        int[] rightTree=new int[(len-1)/2];//需要注意到的是此处建立数组时长度是在不断发生变化的

        System.arraycopy(arrOfPostOrder, (len-1)/2, leftTree, 0,len-i-1);

        boolean rightFlag=true;

        if(i<arrOfPostOrder.length-1){

            rightFlag=verifySequenceOfBST(rightTree);

        }

        return leftFlag&&rightFlag;

    }

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] arr=new int[]{5,7,6,9,11,10,8};

        System.out.println(new VerifySequenceOfBST().verifySequenceOfBST(arr));

    }

}