/*************************************************************************
> File Name: 22_SequenceOfBST.cpp
> Author: Juntaran
> Mail: [email protected]
> Created Time: 2016年08月30日 星期二 20时34分33秒
************************************************************************/ #include <stdio.h>
#include <stdlib.h> // 判断一个数组是不是某个二叉搜索树的后序遍历
bool isSequenceOfBST(int* sequence, int length)
{
if (sequence==NULL || length<=)
return false; int root = sequence[length-]; int i, j; // 二叉搜索树的左子树都小于根
for (i = ; i < length-; ++i)
{
if (sequence[i] > root)
break;
} // 二叉搜索树的右子树都大于根
for (j = i; j < length-; ++j)
{
if (sequence[j] < root)
return false;
} // 递归判断左子树是不是二叉搜索树
bool left = true;
if (i > )
left = isSequenceOfBST(sequence, i); // 递归判断右子树是不是二叉搜索树
bool right = true;
if (i < length-)
right = isSequenceOfBST(sequence+i, length-i-); return (left && right);
} int main()
{
int sequence1[] = {,,,,,,};
int sequence2[] = {,,,};
bool ret1 = isSequenceOfBST(sequence1, );
bool ret2 = isSequenceOfBST(sequence2, );
if (ret1 == true)
printf("ret1 is true\n");
else
printf("ret1 is false\n"); if (ret2 == true)
printf("ret2 is true\n");
else
printf("ret2 is false\n"); return ;
}