CD180 根据后序数组重建搜索二叉树

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = in.nextInt();
        }
        System.out.println(isPost(array, 0, n - 1));
    }

    /**
     * @param array 序列
     * @param first 起始位置
     * @param last  结束位置
     * 0 <= first <= last < array.length
     * @return 是否为二叉搜索树的后序序列
     */
    private static boolean isPost(int[] array, int first, int last) {
        /**
         *                        等价于
         * 左侧均为小值,右侧均为大值 ------> 最后一个小值的位置 + 1 = 第一个大值的位置
         *
         * 详细情况讨论:
         * 情况一:既有左子又有右子
         * 情况一:只有左子
         * 情况二:只有右子
         * 情况四:既没有左子也没有右子
         *
         */
        int less = first - 1;
        int more = last;
        for (int i = first; i < last; i++) {
            if (array[i] < array[last]) {
                less = i;
            } else {
                more = more == last ? i : more;
            }
        }
        return less + 1 == more
                && (less < first || isPost(array, first, less))
                && (more == last || isPost(array, more, last - 1));
    }
}

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

序列结构：| left（值<根）| right（值>根）| head |

isPost(array) :
    return 左子序列的最后一个位置 + 1 == 右子序列的第一个位置 & isPost(left) & isPost(right)

多种情况

1. 根节点既有左子也有右子（节点3）

2. 根节点只有左子（节点 2）

3. 根节点只有右子（节点 4）

4. 只有根节点（节点 1、5）