AcWing 46. 二叉搜索树的后序遍历序列-java
原题链接
简单
作者:
煮不熟的丸子
,
2021-12-06 08:30:42
,
所有人可见
,
阅读 201
class Solution {
public boolean verifySequenceOfBST(int [] seq) {
if(seq == null || seq.length == 0){
return true;
}
int len = seq.length;
//后序遍历,数组的最后一个值是二叉搜索树的根节点
int root = seq[len - 1];
//遍历数组,找出左子树
int i=0;
for(;i<len-1;i++){
if(seq[i] > root){
break;
}
}
//此时i为右子树第一个节点,定义一个左子树数组,左子树有i个节点
int[] left = new int[i];
for(int k = 0;k<i;k++){
left[k]=seq[k];
}
//此时定义j=i为右子树第一个节点
int j = i;
for(;j<len-1;j++){
//判断是否存在不合法的情况(也就是右子树突然出现比根节点小的数)
if(seq[j]<root)
return false;
}
//此时j为len-1,右子树个数为j-i个
int[] right = new int[j-i];
//遍历右子树
for(int k = 0;k<j-i;k++){
right[k]=seq[i+k];
}
boolean left_bool = true;
if(i>0)
left_bool=verifySequenceOfBST(left);
boolean right_bool = true;
if(j>0)
right_bool=verifySequenceOfBST(right);
return left_bool && right_bool;
}
}