【刷算法】判断二叉搜索树的后序遍历序列的数组实现和非递归实现

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

所谓二叉搜索树，也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树以及带有以下性质的二叉树：

若任意结点的左子树不空，则左子树上所有结点的值均大于它的根结点的值；若任意结点的右子树不空，则右子树上所有结点的值均高于它的根节点的值；任意结点的左、右子树也分别为二叉查找树；没有键值相等的结点。

那么对于二叉搜索树的后序遍历的序列来说，最后一个元素即是它的根节点，序列的前某部份元素全部小于最后一个元素，序列的后某部份元素全大于最后一个元素。然后针对这两个别来说，又分别符合这种特性，可以递归的检查下去。

function VerifySquenceOfBST(s)
{
    if(s.length === 0)
        return false;
    return judge(s, 0, s.length-1);
}
function judge(a, l, r) {
    if(l >= r)
        return true;
    var p1 = r;
    while(p1 > l && a[p1-1] > a[r]) {
        p1--;
    }
    var p2 = p1-1;
    while(p2 >= l){
        if(a[p2] > a[r])
            return false;
        p2--;
    }
    
    return judge(a, l, p1-1) && judge(a, p1, r-1);
}

对于一个二叉搜索树来说，根结点的左子树每个节点的值显然大于右子树每个结点的值，所以可以不断的去去掉序列的最后一个值二叉排序树中序遍历，并且把剩下的部份分成高于最后一个值跟大于最后一个值的两个别，只要可分起来那就表明符合二叉搜索树的定义二叉排序树中序遍历，否则就不符合。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-138874-1.html