二叉搜索树的后序遍历序列

题目

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

方法一（最开始自己写的）：

思路

先确定根节点，即root
然后遍历一遍数据，看看是否符合要求
1、左子树均小于根节点
2、右子树均大于根节点
但是这边会有特殊情况（一开始没想到更简单的。只能通过自己设定判断条件flag和pos。）：只有左子树和只有右子树

代码

function VerifySquenceOfBST1(sequence)
{
    if(sequence.length==0)
        return false;
    return check(sequence)
}

function check(sequence){
    if(sequence.length<=1){
        return true;
    }
    var root=sequence[sequence.length-1];//后序遍历最后一个为根节点
    var pos=-1,i,flag=false;
    for(i=0;i<sequence.length-1;i++){
        if(sequence[i]<root&&!flag){
            pos=i;
        }
        else if(sequence[i]>root&&!flag){//转择点，当前i大于root,i-1小于root
            if(pos==-1){//不存在左子树的情况
                flag=true;
                pos=-2;
            }
            else{//左子树存在，即将进入右子树
                flag=true;//只能一次有效
            }
        }
        else if(flag&&sequence[i]<root){//此处表示已遍历完左子树，开始右子树比较
            flag=false;
            pos=-3;
            break;
        }
    }
    // console.log(flag,pos)
    if(!flag&&pos<=-2){
        return false;
    }
    else{
        // console.log(sequence.slice(0,pos+1),sequence.slice(pos+1,sequence.length-1))
        return check(sequence.slice(0,pos+1))&&check(sequence.slice(pos+1,sequence.length-1))
    }
}

方法二（参考别人优化）

思路

后序遍历的最后一个为根节点，且如果是正确的序列，则序列最后一个数值会将该序列的划分成两块，即左子树和右子树。然后递归实现。

代码

function VerifySquenceOfBST(sequence){
    if(!sequence.length)
        return false;
    return Judge(sequence,0,sequence.length-1);
}
function Judge(sequence,start,end){
    if(start>end){
        return true;
    }
    var i=end-1;
    while(i>=start&&sequence[i]>sequence[end]){  //找到左右子树临界点
        i--;
    }
    for(var j=i-1;j>=start;j--){//遍历查看左子树是否符合预期，即所有左子树小于根节点
        if(sequence[j]>sequence[end]){
            return false;
        }
    }
    return Judge(sequence,start,i)&&Judge(sequence,i+1,end-1);
}