【树5】二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 递归实现： public class Solution { public static boolean VerifySquenceOfBST(int [] sequence) { if(sequence == null || sequence.length <= 0) return false; if(sequence.length == 1){ return true; } return VerifySquenceOfBSTCore(sequence, 0, sequence.length - 1); } public static boolean VerifySquenceOfBSTCore(int [] sequence, int start, int end) { if(start >= end) return true; int root = sequence[end]; int index = 0; for(index = start; sequence[index] < root && index < end; index++); for(int i = index; i < end; i++){ if(sequence[i] <= root){ return false; } } return VerifySquenceOfBSTCore(sequence, start, index - 1) && VerifySquenceOfBSTCore(sequence, index, end - 1) ; } } 或 /** *二叉搜索树：左结点值都比根结点小，右结点值都比根结点值大 */ public class Solution { public boolean VerifySquenceOfBST(int [] arrs) { if(arrs==null ||arrs.length<=0) return false; int len=arrs.length; int rootVal=arrs[len-1]; //验证根结点下左子树值是否都小于根结点值 int i=0; for(;i<len-1;i++){ if(arrs[i]>rootVal) break;//此处不能为false,不满足条件可能左子树遍历结束 } int[] leftArrs=new int[i]; System.arraycopy(arrs, 0, leftArrs, 0, i); //验证根结点下右子树值是否都大于根结点值 int j=i; for(;j<len-1;j++){ if(arrs[j]<rootVal) return false; } int[] rightArrs=new int[len-1-i]; System.arraycopy(arrs, i, rightArrs, 0, len-1-i); //递归，继续判断左右子树 boolean left=true; if(i>0){ left=VerifySquenceOfBST(leftArrs); } boolean right=true; if(i<len-1){ right=VerifySquenceOfBST(rightArrs); } return left && true; } }