剑指 Offer 33. 二叉搜索树的后序遍历序列
有点像通过前序和中序遍历重建二叉树
class Solution {
public:
vector<int> nums;
bool verifyPostorder(vector<int>& postorder) {
nums=postorder;
return dfs(0,nums.size()-1);
}
bool dfs(int l,int r){
if(l>=r)return true;
int root=r;
// 右子树的根
int r2=root-1;
int r1=r2;
// 左子树的根，已经按右子树的规则去找左子树的根
while(r1>=0 && nums[r1]>nums[r])r1--;
// 如果左子树中有比root大的值，则导致不合法
for(int i=l;i<=r1;i++) {
if(nums[i]>nums[r])
return false;
}
if(!dfs(l,r1)) return false;
if(!dfs(r1+1,r2)) return false;
return true;
}
};
