题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。例如输{5,7,6,9,11,10,8}返回true 输入{7,4,6,5}返回false
解题思路
1，利用二叉搜索树左《中《右的特性，和后序遍历的特点
2，后序遍历为左右根，则数组末尾为根，然后依据大小找出左子树和右子树
3，递归判断，如果一直符合则为真，否则为假
代码
/** * */ package offerTest; /** * <p> * Title:VerifySquenceOfBST * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月20日 下午9:32:57 */ public class VerifySquenceOfBST { /** * void * * @param args */ public boolean BoolVerifySquenceOfBST(int[] sequence) { if (sequence == null || sequence.length < 1) return false; int len = sequence.length; return helper(sequence, 0, len - 1); } public boolean helper(int[] sequence, int start, int end) { if (start >= end) { return true; } int rootval = sequence[end]; int i = start; for (; i < end; i++) { //犯错位置，这里应该不算根是小于号，不是小于等于 if (sequence[i] > rootval) break; } int j = i; for (; j < end; j++) { if (sequence[j] < rootval) return false; } return helper(sequence, start, i - 1) && helper(sequence, i, end - 1); } public static void main(String[] args) { // TODO Auto-generated method stub } }
