第23题-二叉搜索树的后序遍历序列【JavaScript】

//比如一个二叉树
//    4
//  2   6
// 1 3  5 7
//其后序遍历为[1,3,2,5,7,6,4]
//length为7，起始时sequence.length-1=6
function VerifySquenceOfBST(sequence)
{
    // write code here
    if(sequence.length<=0) return;
    return test(sequence,0,sequence.length-1)
}
function test(sequence,start,end){
    if(start>=end) return true;//空树也是搜索二叉树
    var i=end-1;//第一次执行test时end的位置上一定是整个二叉树的根节点
    //将数组[1,3,2,5,7,6,4]分为小于根节点4的部分和大于4的部分
    //大于4的部分一定是4的右子树，小于4的部分是左子树
    //从4的前一位开始与4比较，只要比4大，就继续向前一位移动，最后i==2，此为为数字2，正好比4小
    while(i>=start&&sequence[i]>sequence[end]){
        i--;
    }
    //判断从第2位再往前的位是否都比4小，如果任意一位大于4，则肯定不是搜索二叉树
    for(var j=i;j>=start;j--){
        if(sequence[j]>sequence[end]){
            return false;
        }
    }
    //对root的左子树重新当成一颗树进行递归判断；
    //对root的右子树重新当成一棵树进行递归判断；
    //左右子树都满足搜索二叉树条件时即整棵树都为搜索二叉树
    return test(sequence,start,i)&&test(sequence,i+1,end-1)
}