剑指offer-23-二叉搜索树的后序遍历
二叉搜索树的后序遍历序列
http://www.nowcoder.com/questionTerminal/a861533d45854474ac791d90e447bafd
思路
了解二叉树和后序遍历的特点就会做了
利用根结点分割左右子树，左<根<右
代码
import java.util.*;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
//二叉树搜索树是左<根<右
//后序遍历是 左右根,在数组中，根结点是最后一个
//前序遍历 根左右，在数组种，根结点是第一个
//中序结点 左根右，在数组种，特点是根结点可以划分左右子树
if(sequence.length<=0){return false;}
return just(sequence);
}
public boolean just(int[] sequence){
if(sequence.length<=2){
return true;
}
int root=sequence[sequence.length-1];
int p=0;
while(p<sequence.length&& sequence[p]<root){
p++;
}
for(int i=p;i<sequence.length-1;i++){
if(sequence[i]<root){
return false;
}
}
return just(Arrays.copyOfRange(sequence,0,p)) &&
just(Arrays.copyOfRange(sequence,p,sequence.length-1));
}
}剑指offer与数据结构 文章被收录于专栏
本专栏包括剑指offer题目和一些刷题用的数据结构，单调栈，树状数组，差分数组，后面还会更新红黑树等较为复杂的数据结构
字节跳动成长空间 780人发布
投递阿里巴巴集团等公司10个岗位 >