判断整数序列是不是二分查找树的后序遍历结果

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。

例如：输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。

但是如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

思路：由后序遍历的特点可知数组的最后一个元素是根节点，若它是某一颗二分查找树的后序便利的结果，那么前面的部分可以连续的分成来那个部分，左边部分是这个根节点的左子树，特点是都小于或等于这个根节点，右边部分是这个根节点的右子树，都大于这个根节点。接下来对于左右子树同样也要满足这样的特点，因而可以很自然的想到递归，每次把数组分成两部分递归下去，若不能分成连续的两部分则肯定不是任何一颗树的后序遍历结果，返回false。

　　基于以上分析，写出代码如下;

 1 bool IsPostOrder(int *arr, int nLeft, int nRight)
 2 {
 3     assert (arr != NULL);
 4 
 5     assert (nLeft >= 0);
 6 
 7     assert (nLeft <= nRight);
 8 
 9     if (nLeft == nRight)
10     {
11         // 只有一个节点，那当然是一颗树的后序遍历
12         return (true);
13     }
14 
15     int i = nLeft;
16     int j = nRight - 1;
17 
18     // 两个标记，防止下面的for循环陷入死循环
19     bool LeftFlag = true;
20     bool RightFlag = true;
21 
22     // 这个数组的功能是将数组分成两部分，它有两个出口
23     // 一个出口是i > j的时候
24     // 另一个出口是i < j, 但i, j都不再移动了
25     for (; i <= j;)
26     {
27         if (LeftFlag || RightFlag)
28         {
29             if (arr[i] <= arr[nRight])
30             {
31                 ++i;
32             }
33             else
34             {
35                 LeftFlag = false;
36             }
37 
38             if (arr[j] > arr[nRight])
39             {
40                 --j;
41             }
42             else
43             {
44                 RightFlag = false;
45             }
46         }
47         else
48         {
49             // i, j都不再移动了，退出循环
50             break;
51         }
52     }
53 
54     if (i < j)
55     {
56         // 非正常退出循环，不能将数组前面部分分成两个连续的部分，因此肯定不是任何一颗树的后序结果
57         return (false);
58     }
59 
60     if (i == nLeft)
61     {
62         // 前面部分都是根节点的右子树，同样的方式确定右子树是否为某颗二分查找树的后序结果
63         return (true && IsPostOrder (arr, i, nRight - 1));
64     }
65     else if (j == (nRight - 1))
66     {
67         // 前面部分都是根节点的左子树，同样的方式确定左子树是否为某颗二分查找树的后序结果
68         return (IsPostOrder (arr, nLeft, nRight - 1) && true);
69     }
70     else
71     {
72         // 分开了两部分，同样的方式处理左右子树是否分别为某颗二分查找树的后序结果
73         return (IsPostOrder (arr, nLeft, i - 1) && (IsPostOrder (arr, i, nRight - 1)));
74     }
75 }

　　一下是部分测试结果：