题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
#include <stack>
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size() == 0) return false;
return order(sequence, 0, sequence.size() - 1);
}
bool order(vector<int>& sequence, int l, int r) {
// 剩一个节点的时候 返回 true
if(l >= r) return true;
int j;
int mid = sequence[r];
// 找到左子树和右子树的分界点，j代表左子树的最后一个索引位置
for(j = l; j <r; j++) {
int cur = sequence[j];
if(cur > mid) break;
}
// 判断所谓的左子树中是否又不合法（不符合二叉搜索树）的元素
for(int i = j; i < r; i++) {
int cur = sequence[i];
if(cur < mid) return false;
}
return order(sequence, l, j-1) && order(sequence, j, r-1);
}
};
使用递归的思路，首先判断当前根节点下是否满足二叉搜索树（左子树的值都小于根节点，右子树的值都大于根节点），然后找到左右子树分界点，递归对左右子树进行判断是否满足二叉搜索树
注意：后续遍历末尾的值就是整棵树的根节点
