二叉搜索树的后续遍历

题目

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

思路

1、二叉搜索树特点

• 二叉搜索树的根节点的左半边都小于根节点
• 二叉搜索树的根节点的左半边都小于根节点

2、分治

• （1）拿出数组最后那个值，因为是后序遍历，所以也就是根节点值
• （2）将数组一分为二。从左向右遍历数组，直到遇到比根节点大的值停止，记录那个下标值。
• （3）将数组安装（2）中的下标值分为左右两部分，从（1）开始递归。

代码

function VerifySquenceOfBST(sequence){
    // write code here
    if(!sequence instanceof Array){
        return false;
    }
    if(sequence.length==0){
        return false;
    }
    return isBinary(sequence);
}
function isBinary(sequence)
{
    // write code here
    if(sequence.length <=0){
        return true;
    }
    var mid = 0;
    var target = sequence.pop();
    while(sequence[mid] < target){
        mid++;
    }
    for(var i=mid;i<sequence.length;i++){
        if(sequence[i] < target){
            return false;
        }
    }
    return isBinary(sequence.slice(0, mid)) && isBinary(sequence.slice(mid));
}