后序遍历:数组的最后一个值是二叉树的根节点
因为是二叉搜索树: 所以前面的值一部分小于根节点,一部分大于根节点,
找到比根节点小的,则为左子树,比根节点大的为右子树,然后递归整个数组即可
(后序遍历,递归) O(n)
Java 代码
class Solution {
public boolean verifySequenceOfBST(int [] sequence) {
// 递归左右边界
// 拿到最后一个元素 即根节点
return dfs(sequence, 0 , sequence.length-1);
}
//左右边界
public boolean dfs(int[] sequence, int l, int r){
if(l >= r){
//因为空树也是一棵二叉搜索树,所以当输入空链表时,应该返回true。
return true;
}
//否则根节点为当前序列的最后一个元素
int root = sequence[r];
//遍历出前半部分,左子树终点,比根节点小的数
int k= l;
while(k < r && sequence[k] < root){
k++;
}
//此时k是右子树的第一个元素
//遍历右子树中所有点,判断是否合法,存在不合法的情况(比如:4,8,6,12,9,14,10)
for(int i=k;i<r;i++){
//右子树的所有点都必须比根节点大
if(sequence[i] < root){
return false;
}
}
//如果合法,同时递归根节点的左边和右边
// 注意这里是 r-1 (去掉root节点)
return dfs(sequence, l , k-1 )&&dfs(sequence, k , r-1);
}
}