1 /************************************************************************* 2     > File Name: 22_SequenceOfBST.cpp 3     > Author: Juntaran 4     > Mail: JuntaranMail@gmail.com 5     > Created Time: 2016年08月30日 星期二 20时34分33秒 6  ************************************************************************/ 7  8 #include <stdio.h> 9 #include <stdlib.h>10 11 // 判断一个数组是不是某个二叉搜索树的后序遍历12 bool isSequenceOfBST(int* sequence, int length)13 {14     if (sequence==NULL || length<=0)15         return false;16     17     int root = sequence[length-1];18     19     int i, j;20     21     // 二叉搜索树的左子树都小于根22     for (i = 0; i < length-1; ++i)23     {24         if (sequence[i] > root)25             break;26     }27     28     // 二叉搜索树的右子树都大于根29     for (j = i; j < length-1; ++j)30     {31         if (sequence[j] < root)32             return false;33     }34     35     // 递归判断左子树是不是二叉搜索树36     bool left = true;37     if (i > 0)38         left = isSequenceOfBST(sequence, i);39     40     // 递归判断右子树是不是二叉搜索树41     bool right = true;42     if (i < length-1)43         right = isSequenceOfBST(sequence+i, length-i-1);44     45     return (left && right);46 }47 48 int main()49 {50     int sequence1[] = {5,7,6,9,11,10,8};51     int sequence2[] = {7,4,5,6};52     bool ret1 = isSequenceOfBST(sequence1, 7);53     bool ret2 = isSequenceOfBST(sequence2, 4);54     if (ret1 == true)55         printf("ret1 is true\n");56     else57         printf("ret1 is false\n");58     59     if (ret2 == true)60         printf("ret2 is true\n");61     else62         printf("ret2 is false\n");63     64     return 0;65 }