46. 二叉搜索树的后序遍历序列
https://www.acwing.com/problem/content/44/
二叉搜索树就是左儿子比根小 右儿子比根大
后续遍历直接获得根节点 然后我们看能不能找到一个分界点 左边的元素都比根节点小 即左儿子 右边的元素都比根节点大 即右儿子 然后递归处理
如果找不到说明无法构建
class Solution {
public:
vector<int>seq;
bool verifySequenceOfBST(vector<int> sequence) {
seq=sequence;
if(sequence.size()==0) return true;
return dfs(0,seq.size()-1);
}
bool dfs(int l,int r){
if(l>=r) return true;
int k=l;
int root=seq[r];
while(k<r && seq[k]<root) k++;
for(int i=k;i<=r;i++){
if(seq[i]<root) return false;
}
return dfs(l,k-1)&&dfs(k,r-1);
}
};