输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

一个二叉树结构是不能仅仅根据后续遍历确定的，但是题目中的二叉树是二叉搜索树，二叉搜索树的性质是节点左子树的值一定小于根节点，右子树的值一定都大于根节点，后续遍历的顺序是先左然后右最后根节点，所以序列的最后一个元素一定是根节点。曾想过既然最后一个元素是根节点，自己能不能根据二叉搜索树的性质和给定的序列能否构建出一个搜索树呢。比如给定测试序列[4,8,6,12,16,14,10]，其中10是根节点，14大于10所以14应该在10的右子树，16大于14，16位于14的右子树，12大于10小于14所以位于14的左子树...... 就这样构建，完成后然后在进行一次后序遍历然后和给定的序列进行比较是否一致。但是这样实在太麻烦了。而且题目中没有给定树的结构，说明题目不需要进行先构建二叉搜索树然后进行后序遍历再比较序列的一致性来求解。所以还是考虑二叉搜索树的性质和树的递归结构，二叉搜索树的节点除了大小性质外，每个子树同样是二叉搜索树。所以完全可以递归求解。求解思路：如果给定的序列符合，根据后续的遍历一定可以找到根节点的左子树的遍历序列和右子书的遍历序列。左边的都一定比根节点小，右边的都比根节点大，有一个不符合就返回false。如果符合就递归的求解左序列和右序列。如果每次递归都符合说明给定序列符合条件。其中遇到的一个问题是如果序列为空应该怎么判断，因为一个二叉搜索树仅仅有左子树或者右子树是可能的，所以我之前判断如果序列元素的数量小于等于1应该返回true。但是如果第一次输入给函数的时候就是空序列，显然是不应该返回true的。所以如果序列为空返回false，后面进行递归之前如果子序列为空就不递归来实现。

function VerifySquenceOfBST($sequence)
{
        // write code here
    $flag = true;
    if(count($sequence)==0){
        return false;
    }
    if(count($sequence)==1){
        return true;
    }
    else{
        $root_val = end($sequence);
        $less_max_idx = -1 ;
        $left = array();
        $right = array();
        for($i = 0;$i < count($sequence);$i++){
            if($sequence[$i]<$root_val){
                $less_max_idx = $i;
            }
        }
        for($i = 0;$i<count($sequence)-1;$i++){
            if($i<=$less_max_idx){
              $left[] = $sequence[$i];
            }else{
               $right[] = $sequence[$i]; 
            }
        }
        //验证左子树,必须都比根节点小
        for($i =0;$i<count($left);$i++){
            if($left[$i] > $root_val){
                return false;
            }
        }
        for($i = 0; $i<count($right); $i++){
            if($right[$i] < $root_val){
                return false;
            }
        }
        if(count($left)>0){
           $flag &= VerifySquenceOfBST($left);
        }
        if($flag&&count($right)>0){ 
            $flag &= VerifySquenceOfBST($right);
        }
        return $flag;
    }
}