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

c++

递归：

数组最后一个元素就是根节点，然后递归判断左右两颗子树

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {
 4         //二叉排序树：左子树比根节点小，右子树比根节点大
 5         //数组最后一个元素就是根节点
 6         if(sequence.size()==0) return false;
 7         if(sequence.size()==1) return true;
 8         //此时只有length>=2时才会才进入下一步
 9         return judge(sequence,0,sequence.size()-1);
10     }
11     bool judge(vector<int> vec,int start,int end){
12         //遍历到最后还没有提前退出返回false，说明是个二叉搜索树，返回true
13         if(start>=end) return true;
14         int i = start;
15         //找右子树，要么找到了右子树i=右子树第一个元素索引，要么遍历到最后没有右子树，这个时候i=end
16         while(i<=end && vec[i]<vec[end]) i++;
17         for(int j=i;j<=end;j++){
18             if(vec[j]<vec[end]) return false;
19         }
20         //这个时候要么找到了右子树中小于root的元素，要么还没有找到，要么就没有右子树
21         return judge(vec,start,i-1) && judge(vec,i,end-1);
22     }
23 };

非递归（这个方法存在问题）：

vec最后一个元素是右子树的根节点，只要保证左子树所有值都小于右子树的根节点就行了。

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {
 4         int len=sequence.size();
 5         if(len==0) return false;
 6         int i=0;
 7         while(--len){
 8             //数组越界问题，i最多到了len，这个时候sequence[len]<sequence[len]条件不成立，i++还会执行，i=len+1了
 9             while(sequence[i++]<sequence[len]);
10             //继续上面的越界问题，此时i=len+1,数组越界了，所以应该加一个条件 i<len，
11             //不加等号是因为：如果=len，第二个while也是不满足条件的，不用判断了，所以直接拍出这个
12             while(sequence[i++]>sequence[len]);
13             //左子树的所有值都<最后一个，右子树所有值都>最后一个，i=len已经是最小了，在小的话，就是false
14             if(i<len) return false;
15             i=0;
16         }
17         return true;
18     }
19 };

[4,5,9,8,12,13,11,10]是BST，交互11<->12就不是，可是这个思路也是true[4,5,9,8,11,13,12,10]. 代码需要改进。