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

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


分析

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

代码如下:

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上:点我前往

来自为知笔记(Wiz)")