输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
后序遍历，根在最后。前半部分为左子树，全部小于根，之后进入右子树，均大于等于根，若在右子树中出现小于根的，则肯定不是后序遍历。
1 class Solution { 2 private: 3 bool find(vector<int> sequence,int l,int r){ 4 int head=l; 5 int tail=r-1; 6 if(l>=r) return true; 7 while(l<r&&sequence[l]<sequence[r]) l++; 8 for(int i=l;i<r;i++){ 9 if(sequence[i]<sequence[r]) 10 return false; 11 } 12 return find(sequence,head,l-1)||find(sequence,l,tail); 13 } 14 public: 15 bool VerifySquenceOfBST(vector<int> sequence) { 16 if(sequence.empty()) return false; 17 return find(sequence,0,sequence.size()-1); 18 19 } 20 };
No。假设输入的数组的任意两个数字都互不相同。
原文：http://www.cnblogs.com/zl1991/p/4765116.html