## 剑指Offer（Java版）：二叉搜索树的后序遍历序列 原

一贱书生

Java代码实现为；

package cglib;

public class DeleteNode {
public boolean verifySequence(int[] array,int start,int end) throws Exception{
if(array == null || array.length < 2)
return true;
if(start < 0){
throw  new Exception("first can't be less than 0");
}
if(end > array.length){
throw new Exception("last can't be greater than the count of the element.");
}
int root = array[end];
//在二叉搜索树中左子树的结点小于根节点
System.out.println("根节点array["+end+"]="+array[end]);
int i = start;
for(; i < end;i++){
System.out.println("比较前array["+i+"]="+array[i]);
if(array[i]>root){//576这三个数都过去
System.out.println("比较后array["+i+"]="+array[i]);
break;
}
}
//在二叉搜索树中右子树的结点大于根节点
int j = i;
for(;j < end;j++){
System.out.println("比较前array["+j+"]="+array[j]);
if(array[j] < root){
System.out.println("比较后array["+j+"]="+array[j]);
return false;
}
}
//判断左子树是不是二叉搜索树
boolean left = true;
if(i >start)
left =verifySequence(array ,start,i-1);
//判断右子树是不是二叉搜索树
boolean right = true;
if(i < end)
right = verifySequence(array,i,end-1);
return (left && right);
}
public static void main(String[] args) throws Exception{
int[] arr={5,7,6,9,11,10,8};
DeleteNode test = new DeleteNode();
System.out.println(test.verifySequence(arr, 0, arr.length-1));
}
}

true

package cglib;

public class DeleteNode {
public boolean verifySequence(int[] array,int start,int end) throws Exception{
if(array == null || array.length < 2)
return true;
if(start < 0){
throw  new Exception("first can't be less than 0");
}
if(end > array.length){
throw new Exception("last can't be greater than the count of the element.");
}
//int root = array[start];
//在二叉搜索树中左子树的结点小于根节点
System.out.println("根节点array["+start+"]="+array[start]);
int i = start+1;

for(; i < end;++i){
System.out.println("i比较前array["+i+"]="+array[i]);
if(array[i]>array[start]){//657这三个数都过去,1,2,3
System.out.println("i比较后array["+i+"]="+array[i]);
break;
}
}
boolean left=true;
boolean right=true;

if (i < end)
{    //判断左子树是不是二叉搜索树
left = verifySequence(array, start + 1, i - 1);
//判断右子树是不是二叉搜索树
right = verifySequence(array, i, end);
}
for (; i <= end; ++i)
{   //在二叉搜索树中右子树的结点大于根节点
if (array[i] < array[start])
return false;
}

return left && right;

}
public static void main(String[] args) throws Exception{
int[] arr={8,6,5,7,10,9,11};
DeleteNode test = new DeleteNode();
System.out.println(test.verifySequence(arr, 0, arr.length-1));
}
}

i比较前array[1]=6
i比较前array[2]=5
i比较前array[3]=7
i比较前array[4]=10
i比较后array[4]=10

i比较前array[2]=5

i比较前array[5]=9
true

### 一贱书生

2018/07/11
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

2018/09/04
0
0
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

01/19
0
0

Android机动车
03/22
0
0
[剑指offer] 二叉搜索树的后序遍历序列

2018/07/01
0
0

37分钟前
3
0

forespider
48分钟前
0
0
mysql函数substring_index的用法

substring_index 按索引字符位进行截取字符串 substring_index（“待截取的字符串”，“截取数据依据的字符”，截取字符的位置N） 第三个参数可正，可负。正数表示索引字符前面的字符串，负数...

echojson
48分钟前
2
0

58分钟前
2
0

spring mvc 整体结构 系统监听到请求 -> 通知tomcat -> 根据web.xml 通知相应的拦截器(spring mvc 通常指DispatcherServlet) --> 检查url是否有相匹配的请求实现 --> 拿到请求实现bean的适配...

59分钟前
3
0