剑指Offer22 判断数组是否为某二叉搜索树的后序遍历

 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
");
56     else
57         printf("ret1 is false
");
58     
59     if (ret2 == true)
60         printf("ret2 is true
");
61     else
62         printf("ret2 is false
");
63     
64     return 0;
65 }