面试题24.二叉搜索树的后序遍历序列

题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序，如果是，则返回true，如果不是则

返回false,假定输入的数组中任意两个数都不相等。

此题目我们以5,7,6,9,11,10,8为例

解题步骤如下:

1.先找到序列的最后一个元素8

2.按照顺序从序列的从前往后遍历，知道遇到第一个大于8的数即9，

3.那么元素9以前为左子树，全部小于跟节点，9以后为右子树，

应该全部大于跟节点，可验证9,11,10全部大于根节点

4.那么现在又产生了两个后序遍历的子序列，一个为5,7,6 一个为11,10,8

5.显然将子序列进行递归1,2,3步骤。递归结束条件是子序列的长度小于等于零。

代码实现如下:

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 bool JustifyBSTAfterOrder(int a[],int length)
 6 {
 7     if(a==NULL||length<=0)
 8         return false;
 9 
10 
11     int RootValue=a[length-1];
12 
13     int i=0;
14     for(;i<length-1;i++)
15     {
16         if(RootValue<a[i])
17             break;
18     }
19 
20     int j=i;
21     for(;j<length-1;j++)
22     {
23         if(RootValue>a[j])
24             return false;
25     }
26 
27     int left=true;
28     if(i>0)
29         left=JustifyBSTAfterOrder(a,i);
30 
31     int right=true;
32     if(j<length-1)
33         right=JustifyBSTAfterOrder(a+i,length-i-1);
34 
35     return (right&&left);
36 }
37 
38 
39 
40 int main()
41 {
42     int a[]={5,7,6,9,11,10,8};
43     int b[]={7,4,6,5};
44 
45     if(JustifyBSTAfterOrder(a,7))
46     {
47         cout<<"Array a is JustifyBSTAfterOrder"<<endl;
48     }
49     else
50     {
51         cout<<"Array a is not JustifyBSTAfterOrder"<<endl;
52     }
53 
54     if(JustifyBSTAfterOrder(b,4))
55     {
56         cout<<"Array b is JustifyBSTAfterOrder"<<endl;
57     }
58     else
59     {
60         cout<<"Array b is not JustifyBSTAfterOrder"<<endl;
61     }
62     system("pause");
63     return 0;
64 }

运行截图如下: