[1,3,2]
true
是上图的后序遍历 ，返回true
[3,1,2]
false
不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false
[5,7,6,9,11,10,8]
true
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
class Solution { bool judge(vector<int>& a, int l, int r){ if(l >= r) return true; int i = r; while(i > l && a[i - 1] > a[r]) --i; for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false; return judge(a, l, i - 1) && (judge(a, i, r - 1)); } public: bool VerifySquenceOfBST(vector<int> a) { if(!a.size()) return false; return judge(a, 0, a.size() - 1); } };