剑指offer第二版-33.二叉搜索树的后序遍历

本系列导航：剑指offer（第二版）java实现导航帖

面试题33：二叉搜索树的后序遍历

题目要求：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，假设输入数组的任意两个数都互不相同。

解题思路：
二叉搜索树的中序遍历是有序的，而此题是后序遍历。
后序遍历可以很容易找到根节点，然后根据二叉搜索树的性质（左子树小于根节点，右子树大于根节点），可以将序列分为根节点的左子树部分与右子树部分，而后递归判断两个子树。

package chapter4;
/**
 * Created by ryder on 2017/7/18.
 * 二叉搜索树的后序遍历序列
 */
public class P179_SequenceOfBST {
    public static boolean verifySquenceOfBST(int[] data){
        //空树
        if(data==null||data.length==0)
            return false;
        return verifySquenceOfBST(data,0,data.length-1);
    }
    public static boolean verifySquenceOfBST(int[] data,int start,int end){
        //数组长度为2，一定能够组成BST
        if(end-start<=1)
            return true;
        int root = data[end];
        int rightStart =0;
        for(int i=0;i<end;i++){
            if(data[i]>root){
                rightStart = i;
                break;
            }
        }
        for(int i=rightStart;i<end;i++){
            if(data[i]<root)
                return false;
        }
        return verifySquenceOfBST(data,start,rightStart-1)&&verifySquenceOfBST(data,rightStart,end-1);
    }
    public static void main(String[] args){
        //            8
        //          /   \
        //         6     10
        //       /  \   / \
        //      5    7 9   11
        int[] data = {5,7,6,9,4,10,8};
        int[] data1 = {5,7,6,9,11,10,8};
        System.out.println(verifySquenceOfBST(data));
        System.out.println(verifySquenceOfBST(data1));
    }
}

运行结果

false
true