剑指offer——二叉搜索树的后续遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解答答案

package com.test;import java.util.Scanner;public class TestSolution {public static void main(String[] args) {MyInputData data=new MyInputData();int[] a = data.input();boolean b=Solution.VerifySquenceOfBST(a);//main函数若想直接调用Solution类下的函数，该函数必须为static类型的，data.output(b);}}
class MyInputData{public int[] input(){//输入一个整型数组Scanner scanner = new Scanner(System.in);System.out.println("请输入一个整型数组，并且以空格为分隔符： ");String[] nums=scanner.nextLine().split(" ");int[] num=new int[nums.length];for(int i=0;i<num.length;i++){num[i]=Integer.parseInt(nums[i]);}return num;//返回整型数组，写法注意}public void output(boolean b){//判断该整型数组是否符合题目要求if(b==true){System.out.println("是");//是二叉搜索树的后序遍历的结果}else {System.out.println("否");//不是二叉搜索树的后序遍历的结果}}
}
class Solution{public static boolean VerifySquenceOfBST(int[] sequence){if(sequence==null || sequence.length==0){//若为空字符数组，则必定不是二叉搜索树的后序遍历的结果return false;}return isLastTree(sequence,0,sequence.length-1);//调用递归函数，判断是否是二叉搜索树的后序遍历的结果}public static boolean isLastTree(int[] sequence,int start,int end){//递归函数if(start>=end){//递归出口return true;}int i=start;for(;i<end;i++){//找到左右子树的分界元素if(sequence[i]>sequence[end]){break;}}for(int j=0;j<i;j++){//左子树元素均小于根元素if(sequence[j]>sequence[end]){return false;}}for(int k=i;k<end;k++){//右子树元素均大于根元素if(sequence[k]<sequence[end]){return false;}}return isLastTree(sequence, 0, i-1) && isLastTree(sequence, i, end-1);//递归}
}