剑指offer系列17：二叉搜索树的后序遍历序列

二叉搜索树（BST树）：首先是二叉树，其次：非叶子结点的左指针指向的结点的值小于其父节点的子树，右指针指向的结点的值大于其父节点的值。

这样就可以形成以个思路，来一个vector，首先把最后一个拿出来，它是根结点。然后从头开始找比它大的第一个数，区分左右子树。第一个比根结点大的树之前都是左子树，其余为右子树。在循环右子树，如果右子树有小于根结点的返回false。以此递归循环即可。

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     bool VerifySquenceOfBST(vector<int> sequence)
 7     {
 8         return myfunction(sequence, 0, sequence.size() - 1);
 9     }
10     bool myfunction(vector<int> sequence, int begain, int end)
11     {
12         if (sequence.empty()||end<begain)
13             return false;
14         int root = sequence[end];
15         int sig = end;//默认没有右子树
16         for (int i = 0; i < end; i++)//找到左右子树分界点
17         {
18             if (sequence[i] > root)
19             {
20                 sig = i;
21                 break;
22             }
23         }
24         for (int i = sig; i < end; i++)//判断右子树的结点是否大于根结点
25         {
26             if (sequence[i] < root)
27                 return false;
28         }
29         bool temp=true;
30         if( sig > begain)//是否存在左子树
31         {
32             temp = myfunction(sequence, 0, sig - 1);
33         }
34         if (temp&&end > sig)
35         {
36             temp = myfunction(sequence, sig, end-1);
37         }
38         return temp;
39     }
40 };
41 int main()
42 {
43     Solution solu;
44     vector<int>  v1 = {5,7,6,9,11,10,8};
45     vector<int>  v2 = { 7,4,6,5 };
46     cout << solu.VerifySquenceOfBST(v1) << endl;
47     cout << solu.VerifySquenceOfBST(v2) << endl;
48     return 0;
49 }

这个题是二叉搜索树，遍历方式是后序。