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

 1 class Solution {
 2 public:
 3     bool verifyPostorder(vector<int>& postorder) 
 4     {
 5          if (postorder.empty())
 6          {
 7              return true;
 8          }
 9 
10          return judge(postorder, 0, postorder.size() -1);
11     }
12 
13     bool judge(vector<int> &a, int left, int right)
14     {
15         if(left >= right) 
16         {
17             return true;
18         }
19         
20         // 从后面开始找
21         int i = right;
22         while(i > left && a[i - 1] > a[right]) 
23         {
24             --i;     // 找到比根小的坐标
25         }
26         
27         // 从前面开始找 star到i-1应该比根小
28         for(int j = left; j < i - 1; ++j) 
29         {
30             if(a[j] > a[right]) 
31             {
32                 return false;
33             }
34         }
35         return judge(a, left, i - 1) && (judge(a, i,right - 1));
36     }
37 
38 };