1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Solution {public: bool VerifySquenceOfBST(vector<int> sequence) { int size=sequence.size(); if(size==0)return false; else if(size==1)return true; int root=sequence.back(); int i,iLeftEnd; bool result=true; for(i=0;i<size-1;i++) { if(sequence[i]>root) { iLeftEnd=i; break; } } for(;i<size-1;i++) { if(sequence[i]<root) return false; } if(iLeftEnd>0)//保证左子树有成员才判断，避免迭代空vector { vector<int>leftson; leftson.assign(sequence.begin(),sequence.begin()+iLeftEnd); result=VerifySquenceOfBST(leftson); if(!result)return false; } if(iLeftEnd<size-1)//保证右子树有成员才判断，避免迭代空vector { vector<int>rightson; rightson.assign(sequence.begin()+iLeftEnd,sequence.end()-1); result=VerifySquenceOfBST(rightson); } return result; }}; |
原文：http://www.cnblogs.com/zhxshseu/p/5285137.html