现在的位置: 首页 > 综合 > 正文

判断一个整数数组是不是二叉搜索树的后序遍历序列

2013年12月07日 ⁄ 综合 ⁄ 共 514字 ⁄ 字号 评论关闭

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。

           如果是返回true,否则返回false

 

bool isPostSequence(int *num,int n)
{
    if(num==NULL || n<=0)
    {
        //throw new exception("the input is error");
    }
    int *pstart=num,*pend=num+n;
    return isPostSequenceByIndex(pstart,pend);
    
}

bool isPostSequenceByIndex(int *pstart,int *pend)
{
    if(pstart==pend)
    {
        return true;
    }
    int *cur=pstart;
    while(cur<pend)
    {
        if(*cur<*pend)
        {
            cur++;
        }else
        {
            break;
        }
    }
    int *mid=cur;
    while(cur<pend)
    {
        if(*mid<*pend)
        {
            return false;
        }else
        {
            cur++;
        }
    }
return isPostSequenceByIndex(pstart,mid) && isPostSequenceByIndex(mid+1, pend);
}


抱歉!评论已关闭.