题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length==0)return false; return VerifySquence(sequence,0,sequence.length-1); } public boolean VerifySquence(int[] sequence,int start,int end){ if(start>=end)return true;//中途没false就一直遍历 int i = start; while(i<end&&sequence[i]<sequence[end])i++; for(int j = i;j<end;j++){//end处就是根结点的值 if(sequence[j]<sequence[end])return false; }//分治,递归判断左右序列,注意右子树要去掉end处的根结点 return VerifySquence(sequence,start,i-1)&&VerifySquence(sequence,i,end-1); } }