题解 | #二叉搜索树的后序遍历序列#

import java.util.Arrays;

public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length == 0) return false; if(sequence.length == 1) return true;

    int root = sequence[sequence.length - 1];
    if(sequence.length == 2) {
    	return true;
    }
    int dividePoint = dividePoint(sequence, root);
    if(dividePoint == -1) {
    	int[] left1 = Arrays.copyOfRange(sequence, 0, sequence.length-1);
    	if(greaterAll(left1, root)) {
    		if(VerifySquenceOfBST(left1)) return true;        		
    	}else return false;
    }
    if(dividePoint == 0) {
    	int[] right1 = Arrays.copyOfRange(sequence, 0, sequence.length-1);
    	if(smallerAll(right1, root)) {
    		if(VerifySquenceOfBST(right1)) return true;        		
    	}else return false;
    }
    
    int[] left = Arrays.copyOfRange(sequence, 0, dividePoint);
    int[] right = Arrays.copyOfRange(sequence, dividePoint, sequence.length-1);
    
    if(greaterAll(left,root) && smallerAll(right,root)) {
    	if(VerifySquenceOfBST(left) && VerifySquenceOfBST(right)) return true;
    }
    
    
	return false;
}

public boolean greaterAll(int[] a,int root) {
	for(int i = 0;i < a.length;i++) {
		if(root < a[i]) break;
		if(root>a[i] && i==a.length-1) return true;
	}
	
	return false;
}

public boolean smallerAll(int[] a,int root) {
	for(int i = 0;i < a.length;i++) {
		if(root > a[i]) break;
		if(root<a[i] && i==a.length-1) return true;
	}
	
	return false;
}

public int dividePoint(int[] a,int root) {
	int num = -1;
	for(int i = 0;i < a.length;i++) {
		if(a[i] > root) {
			num = i;
			break;
		}
	}
	return num;
}

}