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

概述c++ 递归：数组最后一个元素就是根节点，然后递归判断左右两颗子树 1 class Solution { 2 public: 3 bool VerifySquenceOfBST(vector<int> sequence) { 4 //二叉排序树：左子树比根节点小，右子树比根节点大 5 //数组最后一个元素就是根节点 6

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，说明是个二叉搜索树，返回true13         if(start>=end) return true;14         int i = start;15         //找右子树，要么找到了右子树i=右子树第一个元素索引，要么遍历到最后没有右子树，这个时候i=end16         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已经是最小了，在小的话，就是false14             if(i<len) return false;15             i=0;16         }17         return true;18     }19 };