Java实现判断一个序列是否为某二叉搜索树的后序遍历(加图解)
题目描述:
输入一个整数数组,判断该数组是不是某二叉树的后序遍历 的结果。如果是则输出“YES”,否则输出“NO”。假设输入的数组的任意两个数字都互不相同。
在解决这个问题之前,首先要弄清楚两个问题:
(1)简单了解什么是二叉搜索树?
(2)后序遍历的方法
1.二叉搜索树的定义:
二叉搜索树又叫二叉排序树也叫二叉查找树(Binary Search Tree),二叉排序树或者是一棵空树,或者是具有以下特点的二叉树:
(1)若左子树不为null,则左子树上的结点的值均小于它的根结点的值;
(2)若右子树不为null,则右子树上的结点的值均大于或等于它的根结点的值;
(3)左右子树也分别为二叉排序树;
如下图就是一棵二叉搜索树:
2.后序遍历的顺序:访问左子树---->访问右子树---->访问根结点,然后利用递归的思想,重复此操作。
上图的二叉搜索树的后序遍历序列为:[3,4,6,5,8,10,9,7]
依此序列为例,对该问题展开阐述:
3.设计思路:
(1)将输入的序列存储在一维数组中,若该数组的长度为0【即该树为空】,return false;
(2)否则就根据二叉搜索树的性质,对该数组进行分析,因为是后序遍历结果,所以数组中的最后一个元素一定是这棵二叉搜索树的根结点,在其之前且比它小的元素一定是其左子树上的所有结点,比它大的元素一定是其右子树上的所有元素(该过程即为比较筛选的过程)。
图解过程如下;
程序代码:
public class PosTree {
public boolean VerifySquenceOfBST(int []sequence){
if(sequence.length==0) return false;
return IsTreeBST(sequence,0,sequence.length-1);
}
public boolean IsTreeBST(int[] sequence, int start, int end) {
if(end<=start) return true;
int i=start;
for(;i<end;i++){
if(sequence[i]>sequence[end]) break;
}
for(int j=i;j<end;j++){
if(sequence[j]<sequence[end]) return false;
}
return IsTreeBST(sequence,start,i-1)
&& IsTreeBST(sequence,i,end-1);
}
}