二叉搜索树后序遍历序列 C语言解题思路

思路：例如数组：[1,2,7,4,6,5,3] 搜索树，意思是任意节点，左孩子均小于节点值，右孩子均大于节点值

根据后序遍历，即后根遍历，很容易确定数组最后一个为根节点。此时根据根节点将数组分为左子树，右子树两部分，需要保证左右子树均为二叉搜索树。典型的递归思想，先根据数组末位将数组分为两部分，再分别对两部分执行判断即可。

注意：根据题目要求，空数组也不是二叉搜索树，因此设置一个全局变量，判断递归函数中初始数组是否为空。

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param sequence int整型一维数组 
 * @param sequenceLen int sequence数组长度
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static int flag=0;
bool VerifySquenceOfBST(int* sequence, int sequenceLen ) {
   //判断初始数组是否为空
    if(flag==0&&sequenceLen==0)
        return false;
    flag=1;
    //初始数组不为空，flag置为1,当数组元素个数为0或者1，肯定为一个搜索树，返回true
    if(sequenceLen==1||sequenceLen==0)
        return true;
    int i=0,k=0;
    //寻找第一个大于根节点的位置，也就是左右子树的分割位置
    //经过左边元素会均小于根节点
    while(sequence[i]<sequence[sequenceLen-1])
        i++;
    //记录这个位置
    k=i;
    //判断右边节点是否都大于根节点，如果都大于，i最后会指向根节点
    while(sequence[i]>sequence[sequenceLen-1])
        i++;
    //说明提前出现了小于根节点的值
    if(i<sequenceLen-1)
            return false;
    //递归判断左右子树是否为二叉搜索树
    if(VerifySquenceOfBST(sequence, k) && VerifySquenceOfBST(&sequence[k], sequenceLen-k-1))
        return true;
    return false;
}