46. 二叉搜索树的后序遍历序列
作者:
catlle
,
2022-09-14 18:11:31
,
所有人可见
,
阅读 167
class Solution {
public:
vector<int> seq;
bool verifySequenceOfBST(vector<int> sequence) {
seq = sequence;
return dfs(0, seq.size() - 1);
}
bool dfs(int l, int r){
//当树被遍历完之后就返回TRUE
if(l >= r)
return true;
//每次遍历的区间的最后一位是根节点
int root = seq[r];
int k = l;
//找分界点
while(seq[k] < root && k < r) k++;
//如果分界点右边有比根节点小的数就返回FALSE
for(int i = k; i < r; i++)
if(seq[i] < root)
return false;
//继续遍历分界后的区间
return dfs(l, k - 1) && dfs(k, r - 1);
}
};