二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

 1 class Solution {
 2 public:
 3    bool fun(vector<int> arr,int bg,int end)
 4     {
 5         if (bg >= end)
 6             return 1;
 7         int last = arr[end];
 8         int i = end - 1;
 9         while(i >= bg && last < arr[i])
10             --i;
11         int fend = i;
12         bool is = fun(arr,i+1,end -1);
13         if (!is)
14             return 0;
15         for (i;i >= bg ; --i)
16         {
17             if(arr[i] > last)
18                 return 0;
19         }
20         return fun(arr,bg,fend);
21     }
22     bool VerifySquenceOfBST(vector<int> sequence) {
23         if(sequence.size() == 0)
24             return 0;
25         return fun(sequence,0,sequence.size()-1);
26     }
27 };