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

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return VerifySquenceOfBST1(sequence, 0, sequence.length - 1);
    }
    public boolean VerifySquenceOfBST1(int [] sequence, int star, int end) {
        if (star >= end) {
            return true;
        }
        int root = sequence[end];
        int starIndex;
        for (starIndex = star; starIndex < end &&
                sequence[starIndex] < root; starIndex++);
        for (int i = star; i < starIndex; i++) {
            if (sequence[i] >= root) {
                return false;
            }
        }
        for (int i = starIndex; i < end; i++) {
            if (sequence[i] <= root) {
                return false;
            }
        }
        return VerifySquenceOfBST1(sequence, star, starIndex - 1) &&
               VerifySquenceOfBST1(sequence, starIndex, end - 1);
    }
}