剑指Offer-Java-二叉搜索树的后序遍历序列
【摘要】
二叉搜索树的后序遍历序列
题目:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
代码:
...
package com.sjsq.test;
/**
* @author shuijianshiqing
* @date 2020/5/25 21:26
*/
/**
* 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历
* 的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意
* 两个数字都互不相同。
*/
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
// 为空时为true
if(sequence == null || sequence.length == 0){
return false;
}
return helqVerifty(sequence,0,sequence.length-1);
}
public boolean helqVerifty(int seq[],int start,int end){
if(start >= end){
return true;
}
int key = seq[end];
int i;
// 找到左右子树的分界点
for(i = start; i < end; i++){
if(seq[i] > key){
break;
}
}
// 判断从右子树有有没有比key小的,如果有则返回false
for(int j = i; j < end; j++){
if(seq[j] < key){
return false;
}
}
// 判断左子树和右子树是否符合
return helqVerifty(seq,start,i-1) && helqVerifty(seq,i,end-1);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
文章来源: blog.csdn.net,作者:水坚石青,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/helongqiang/article/details/106343074
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)