[数据结构与算法]二叉搜索树的后序遍历

JZ23

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&&tqId=11176&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

//思路：最后一个数字是根x，确保前部分元素都小于x，后部分元素都大于x（递归）

public class Solution {
? ? public boolean VerifySquenceOfBST(int [] sequence) {
? ? ? ? if(sequence.length<1||sequence==null) //树为空 false
? ? ? ? ? ? return false;
? ? ? ? if(sequence.length==1) ?//树只有根，true
? ? ? ? ? ? return true;
? ? ? ? return dfs(sequence,0,sequence.length-1);
? ? }
? ? public boolean dfs(int[] seq,int start,int end){
? ? ? ? if(start>end)
? ? ? ? ? ? return true;
? ? ? ? int index = start; ?//开始寻找小于x和大于x的分界
? ? ? ? while(seq[end]>seq[index]&&index<end-1)
? ? ? ? ? ? index++; ?//index为第一个大于x的值的下标
? ? ? ? for(int i=end-1;i>index;i--){
? ? ? ? ? ? if(seq[i]<seq[end]){ ?//若大于x的部分还有小于x的值 则不为二叉搜索树
? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dfs(seq,start,index-1)&&dfs(seq,index,end-1);
? ? }
}