地址 https://www.acwing.com/solution/acwing/content/3959/
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。
假设输入的数组的任意两个数字都互不相同。
样例
输入：[4, 8, 6, 12, 16, 14, 10] 输出：true
根据二叉树的定义来看 最后一个是根节点 前面的序列中必须存在一个拐点 拐点前后的值 要么均大于根 要么均小于根
那么可以将序列与根节点比较，递归逐步缩小序列范围， 注意边界条件 比如全部比根节点大或者全部比根节点小。
最后设置退出条件。
class Solution { public: bool verifySequenceOfBSTInner(vector<int> sequence) { if(sequence.size() < 1) return true; int root = sequence.back(); int flag = 0; int idx = -1; for(int i =0 ; i<sequence.size()-1;i++ ){ if(sequence[i] > root && flag == 0){ flag = 1;idx = i; }else if(sequence[i] < root && flag == 1){ return false; } } bool ret1 = true; vector<int> tmp1; if(idx > 0){ tmp1 = vector<int>(sequence.begin(),sequence.begin()+idx); ret1 = verifySequenceOfBSTInner(tmp1); } bool ret2 = true; vector<int> tmp2; if(idx < sequence.size()-1){ tmp2 = vector<int>(sequence.begin()+idx,sequence.end()-1); ret2 = verifySequenceOfBSTInner(tmp2); } return ret1&& ret2; } bool verifySequenceOfBST(vector<int> sequence) { return verifySequenceOfBSTInner(sequence); } }; 作者：defddr 链接：https://www.acwing.com/solution/acwing/content/3959/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。