验证二叉搜索树的序列是否有效（23）

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

思路&＃xff1a;
找住二叉查找树&＃xff08;Binary Search Tree,BST)的特点&＃xff1a;左子树<根<右子树
使用分治思想和递归思想

package swordToOffer._23_VerifySquenceOfBST;public class Solution {public boolean VerifySquenceOfBST(int [] sequence) {if(sequence.length&＃61;&＃61;0){return false;}return judge(sequence,0,sequence.length-1);}//用于判断该该子树右子树是否比根结点大&＃xff0c;左子树是否比根结点小public boolean judge(int[] seq,int start,int root){//写出递归终止条件,一定是>&＃61;&＃xff0c;不能只写>&＃xff0c;因为当只有左子树时&＃xff0c;会出现start>root情况&＃xff0c;//具体往下看**处if(start>&＃61;root){return true;}int i&＃61;start;//从前往后找&＃xff0c;找到根结点在序列中的位置&＃xff08;此时根节点左边都比根节点小&＃xff09;while(i>&＃61;start && i<root){//最后一个即为根结点root&＃xff0c;如果大于root&＃xff0c;则该位置i为右子树序列的开始位置if(seq[i]>seq[root]){break;}i&＃43;&＃43;;}int boudaryIndex&＃61;i;//继续判断根结点右边&＃xff0c;应该都要比根节点大。//如果是从后往前找&＃xff08;此时根节点右边都比根节点大&＃xff09;,要继续判断根节点左边都比根结点小。while(i<root){if(seq[i]<seq[root]){return false;}i&＃43;&＃43;;}//左右分治&＃xff0c;不断递归&＃xff0c;直到返回结果//**当只有左子树时&＃xff0c;boudaryIndex&＃61;root&＃xff0c;root-1//会出现start>root情况&＃xff0c;由于没有关于start>root的终止操作&＃xff0c;此时右半部分会不断递归&＃xff0c;直到栈溢出return judge(seq,start,boudaryIndex-1)&& judge(seq,boudaryIndex,root-1);}}