024-二叉搜索树的后序遍历序列.md

面试题24 二叉搜索树的后序遍历序列

题目：

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

package algorithm.foroffer.top30;

/**
 * Created by liyazhou on 2017/5/28.
 * 面试题24：二叉搜索树的后序遍历序列
 *
 * 题目：
 *      输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 *      如果是则返回 true，否则返回 false。
 *      假设输入的数组的任意两个数字都互不相同。
 *
 * 问题：
 *      1. 二叉搜索树的性质
 *      2. 二叉树的后序遍历结果的特点
 *      3. 递归
 *
 * 思路：
 *      1. 二叉搜索树的性质，根结点比左孩子大，根结点比右孩子小
 *      2. 二叉树的后序遍历结果，最后的一个结点总是根结点
 *      3. 以最后一个元素作为分割点，将后序遍历结果分为两部分，其左子树和右子树的后序遍历结果
 *         判断每一个棵子树的是否满足条件，根结点比左孩子大，根结点比右孩子小
 *
 */
public class Test24 {

    public static boolean vertifySeqOfBST(int[] postorder, int start, int end){
        // System.out.println(String.format("start, end = %d, %d", start, end));
        // 应该在传入参数之前判断，免得每次递归都得进行判断
        if (postorder == null) return false;

        int split;
        for (split = start; split < end - 1; split++){  // 最后一个元素是根结点，不判断
            if (postorder[split] > postorder[end-1])  break;
        }


        // 递归终止条件
        // 如果根结点比其右孩子大，则返回 false
        for (int i = split; i < end; i++)
            if (postorder[i] < postorder[end - 1]) return false;


        boolean left = true;
        // 有条件的递归，其递归终止条件是 split <= start
        if (split > start) // 该区间的元素大于或者等于 2 个
            left = vertifySeqOfBST(postorder, start, split);

        boolean right = true;
        // 有条件的递归，其递归终止条件是 split >= end-1
        if (split < end-1)  // 该区间的元素大于或者等于 2 个
            right = vertifySeqOfBST(postorder, split, end-1); // 最后一个元素是根结点，不进入下一轮

        return (left && right);
    }

    public static void main(String[] args){
        int[][] seqs = {
                {5, 7, 6, 9, 11, 10, 8},
                {5, 7, 6, 9, 11, 5, 8}
        };

        for (int i = 0; i < seqs.length; i++)
            System.out.println(Test24.vertifySeqOfBST(seqs[i], 0, seqs[i].length));
    }

}