题解 | #二叉搜索树的后序遍历序列#

递归

#include<stdbool.h>

bool Check_core(int *a, int Len)
{
    int index;
    int i;
    bool flag = false;
    if (a == NULL || Len <= 1)
        return true;
    
    for (i = 0; i < Len; i++)
    {
        if (!flag&&a[i] > a[Len - 1])
        {
            index = i;
            flag = true;
        }
        if (flag && a[i] < a[Len - 1])
            return false;
    }
    if (i == Len || index == 0)
        return Check_core(a, Len - 1);
    else
        return Check_core(a, index)&& Check_core(a+index, Len- index-1);
        
}

bool VerifySquenceOfBST(int* sequence, int sequenceLen ) {
    if (sequence == NULL || sequenceLen <= 0)
        return false;
    return Check_core(sequence, sequenceLen);
}