y总视频里的代码有点问题,边界改一下就好了,但是刚才做的时候有点莫名其妙的问题没过,后来写了一遍一模一样的代码又对了,真的太奇怪了。
class Solution {
public:
vector<int> seq;
bool dfs(int l, int r){
if (l >= r) return true;
// 找到根节点是后序遍历的最后一个节点
int root = seq[r];
int k = l;
// k定位到第一个大于root的节点,也就是右子树的第一个节点
while(k < r && seq[k] < root) k++;
// 判断在右子树里面是否有小于root的节点,若有这说明不满足条件
for (int i = k; i < r; i++) {
if (seq[i] < root) return false;
}
// 递归遍历左右子树,左[l,k - 1],右[k, r - 1];
return dfs(l, k - 1) && dfs(k, r - 1);
}
bool verifySequenceOfBST(vector<int> sequence) {
seq = sequence;
return dfs(0, seq.size() - 1);
}
};