后续遍历性质要牢记,最后一个节点为根节点。
class Solution {
public:
vector<int> seq; //把seq变为全局数组,便于dfs函数调用,否则每次调用dfs都要传一个数组进去
bool verifySequenceOfBST(vector<int> sequence) {
seq = sequence;
return dfs(0, seq.size() - 1);
}
bool dfs(int l, int r)
{
if (l >= r) return true; //当数为空时,返回true
int root = seq[r]; //最后一个元素为根节点
int k = l;
while (k < r && seq[k] < root) k ++ ; //从前往后找第一个大于root的元素
for (int i = k; i < r; i ++ ) //判断右子树节点是否都大于根节点
if (seq[i] < root)
return false; //若小于则返回false
return dfs(l, k - 1) && dfs(k, r - 1); //继续dfs
}
};