《剑指offer》Java实现--二叉搜索树的后续遍历序列

题目描述

    输入一个整数数组，判断该数组是不是二叉搜索树的后续遍历结果，假设输入数组的元素互不相等。

解题思路

    如下图的后续遍历序列为squence{5,7,6,9,11,10,8}，对于序列数组squence，最后一个元素8即为树的根节点，我们以根节点为标准，从左往右搜索序列，左子树中的节点均小于根节点得到左子树序列{5,7,6}，右子树中的节点均大于根节点得到右子树序列{9,11,10}，左右子树以此递归搜索判断。

二叉搜索树

Java代码实现

/**
 * 给定一个数组形式的数列判断是否二叉搜索树的后续遍历，递归解法
 * @author Administrator
 * @version 2018/10/12
 */
public class Exe34_VerifySquenceOfBST {

    public static void main(String[] args) {
        
        int[] squence={5,7,6,9,11,10,8};
        System.out.println(verifySequenceOfBST(squence, 0, squence.length-1));

    }
    
    public static boolean verifySequenceOfBST(int[] squence,int startIndex,int endIndex) {
        
        if(squence==null||startIndex<0||startIndex>squence.length-1
            ||endIndex<startIndex||endIndex>squence.length-1) return false;
        else {
            //首先根据根节点(序列最后一个)将序列分成左右子树序列并判断合法性
            int root=squence[endIndex];
            int i=startIndex;
            for(;i<endIndex;i++){
                if(squence[i]>root)
                    break;
            }
            int j=i;
            for(;j<endIndex;j++){
                if(squence[j]<root)
                    return false;
            }
            
            //递归判断子序列的合法性
            boolean isLeftLeagel=true;
            if(startIndex<i-1){//注意这里条件判断，如果子序列长度为0，那么它也是合法的
                isLeftLeagel=verifySequenceOfBST(squence, startIndex, i-1);
            }
            boolean isRightLeagel=true;
            if(i<endIndex-1){//注意这里条件判断，如果子序列长度为0，那么它也是合法的
                isRightLeagel=verifySequenceOfBST(squence, i, endIndex-1);
            }
            
            return isLeftLeagel&&isRightLeagel;
        }
    
    }

}