题解 | 二叉搜索树的后序遍历序列

采用递归的思想，分别对二叉树的左右两边分别进行处理，最后对各种情况进行判断

import java.util.*;
public class Solution {

    boolean flag = true;

    public int[] getResult(int sequence[]) {
        int n = sequence.length;
        if (n == 1) return new int[] {sequence[0], sequence[0]};
        else if (n == 2) {
            if (sequence[0] > sequence[1])
                return new int[] {sequence[1], sequence[0]};
            else return new int[] {sequence[0], sequence[1]};
        } else {
            int idx = 0;
            while (idx < n && sequence[idx] < sequence[n - 1]) idx++;
            int left[] = new int[idx];
            for (int i = 0; i < idx; i++) left[i] = sequence[i];
            int right[] = new int[n - idx - 1];
            for (int i = 0; i < n - idx - 1; i++) {
                int x = sequence[i + idx];
                if (x < sequence[n - 1]) flag = false;
                right[i] = x;
            }
            if (left.length == 0) {
                int r[] = getResult(right);
                if (r[0] < sequence[n - 1]) flag = false;
                return new int[] {sequence[n - 1], r[1]};
            } else if (right.length == 0) {
                int l[] = getResult(left);
                if (l[1] > sequence[n - 1]) flag = false;
                return new int[] {l[0], sequence[n - 1]};
            }
            int l[] = getResult(left);
            int r[] = getResult(right);
            if (l[1] > sequence[n - 1] || sequence[n - 1] > right[0]) flag = false;
            return new int[] {l[0], r[1]};
        }
    }

    public boolean VerifySquenceOfBST(int [] sequence) {
        int n = sequence.length;
        if (n == 0) return false;
        else if (n == 1) return true;
        getResult(sequence);
        return flag;
    }
}