判断一个序列是否为某二叉搜索树的后续遍历结果

问题描述：输入一个整数数组，判断该数组是不是某个二叉搜索树的后续遍历结果。如果是返回true，不是返回false。假设输入的数组的任意两个数字互不相同。

分析：二叉搜索树的根节点的左子树值小于根节点，右子树值大于根节点。根节点位于序列的尾部。递归判断节点的左右子树是否为二叉搜索树的后续遍历。

代码如下：

package com.wyl.sequence;

import java.util.Arrays;

/**
 * 判断一个序列是否为某个二叉搜索树的后序遍历序列
 * 思想：序列的最后一个值是树根节点的值，先遍历左子树，其值比根节点小，右子树的值比根节点大
 * @author wyl
 *
 */
public class BinarySearchTree {
    /**
     * 判断序列是否为二叉搜索树的一个可能后续遍历
     * @param sequence 待判断序列
     * @param length 序列长度
     * @return 序列是否为可能的后序遍历序列
     */
    public boolean verifyBST(int[] sequence, int length){
        if(sequence == null || length <= 0){
            return false;
        }
        int root = sequence[length - 1]; //序列的最后一个值为根节点的值
        //二叉搜索树的左节点值小于根节点
        int i = 0 ;
        for(;i<length-1;i++){
            if(sequence[i] > root){
                break;
            }
        }
        //二叉搜索树的右节点值大于根节点
        int j = i ;
        for(;j<length-1;j++){
            if(sequence[j] < root){
                return false;
            }
        }
        
        //判断左子树是否为二叉搜索树的后续遍历
        boolean left = true; //左子树为1个节点
        if(i>0){
            left = verifyBST(sequence, i);
        }
        
        //判断左子树是否为二叉搜索树的后续遍历
        boolean right = true;//右子树为1个节点
        if(i<length-1){
            int [] newData; //用来保存右子树
            newData = Arrays.copyOfRange(sequence, i, length-1);
            right = verifyBST(newData, length-1-i);
        }
        if(left && right){
            return true;
        }
        return false;
    }
    
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] sequence = {5,7,6,9,12,11,8};
        boolean b = bst.verifyBST(sequence, sequence.length);
        System.out.println(b);
    }
}