• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

剑指offer解题报告(Java版)——判断一个数组是否是二叉搜索树的后序遍历序列 24

admin

11月 28, 2021

引言

   

继续二叉树,这个题考的知识点是二叉树的后续遍历

   

分析问题

   

对于一个二叉树的后序遍历序列来说,最后一个数一定是根节点,然后前面的数中,从最开始到第一个大于根节点的数都是左子树中的数,而后面到倒数第二个数应该都是大于根节点的,是右子树,如果后面的数中有小于根节点的,那么说明这个序列不是二叉搜索树的后序遍历序列

   

解决问题

   

同样是用递归去做,首先要考虑Corner Case,如果array为空,那么返回false

   

然后找到根节点,根节点是array最后一个数,从0开始找,找到第一个大于root的数

   

那么0i-1的值就是左子树中的数

   

然后从iarray.length-2遍历,如果有小于root的数,那么这个序列肯定不是后序遍历序列

如果没有,那么iarray.length-2就是右子树中的数

   

那么就去看左子树中的子序列和右子树中的那些子序列是否满足条件

   

注意这里需要用到数组的复制函数,不然会出问题

   

public boolean verifySequenceOfBST(int[] array)

{

if(array==null || array.length<=0)

return false;

int root=array[array.length-1];

int i=0;

for(;i<array.length-1;++i)

{

if(array[i]>root)

{

break;

}

}

int j=i;

for (;j < array.length-1; ++j) {

if (array[j]<root) {

return false;

}

}

boolean leftFlag=true;

if (i>0) {

leftFlag=verifySequenceOfBST(Arrays.copyOfRange(array,0,i));

}

boolean rightFlag=true;

if (i<array.length-1) {

rightFlag=verifySequenceOfBST(Arrays.copyOfRange(array,i,array.length-1));

}

return leftFlag&&rightFlag;

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注