面试题24：二叉搜索时的后序遍历序列

题目：输入一个整数数组，判断该数组是不是某二叉搜索时的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任一两个数字都不相同。

分析

我们先假设该数组是某颗二叉搜索树的后序遍历序列，则它有如下性质：

• 数组最后一个元素是该二叉树的根节点；
• 若数组为arr，长度为n，则arr[0..k-1]<arr[n-1],arr[k..n-2]>arr[n-1]，(0<=k<=n-1)；
• 对arr[0..k-1]和arr[k..n-2]同样适用于这些规律； 不难看出，这是一个递归的思想。数组中前面一部分数字会小于最后一个数字（对应于根节点的左子树），后面一部分数字会大于最后一个数字（对应于根节点的右子树），因此可以递归地对他们进行判断。

代码如下：

class ArgIsError{};

template
bool compair(const T& t1,const T& t2)
{
    return t1>t2;
}

template
bool IsMax(const vector& v,int start,int end,const T& t)throw (ArgIsError)
{
    if(v.size()end)
        throw ArgIsError();
    int i;
    for(i=start;i<end;++i)
    {
        if(compair(v[i],t))
            return false;
    }
    return true;
}
template
bool IsMin(const vector&amp; v,int start,int end,const T&amp; t)throw (ArgIsError)
{
    if(v.size()end)
        throw ArgIsError();
    int i;
    for(i=start;i<end;++i)
    {
        if(!compair(v[i],t))
            return false;
    }
    return true;
}

template
bool VerifySquenceOfBST(const vector&amp; sequence)
{
    if(sequence.size()=0;--i)
    {
        if(sequence[i]<sequence[length-1])
        {
            left=0;
            right=i+1;
            break;
        }
    }
    try
    {
        if(!IsMax(sequence,left,right,sequence[length-1]) || !IsMin(sequence,right,length-1,sequence[length-1]))
        {
            return false;
        }
    }
    catch(ArgIsError&amp;)
    {
        ;
    }
    vector lseq(sequence.begin()+left,sequence.begin()+right),rseq(sequence.begin()+right,sequence.begin()+length-1);
    if(VerifySquenceOfBST(lseq) &amp;&amp; VerifySquenceOfBST(rseq))
    {
        return true;
    }
    else
    {
        return false;
    }
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往