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

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if(sequence.length == 0) return false;
        return check(sequence, 0, sequence.length - 1);
    }
    boolean check(int[] sequence, int l, int r) {
        if(l >= r) return true;

        int rootVal = sequence[r];

        // 找出右子树
        int i = r - 1;
        while(i >= l && sequence[i] > rootVal) {
            i--;
        }

        // 验证左子树
        int j = i;
        for(; i >= l; i--) {
            if(sequence[i] > rootVal) return false;
        }
        return check(sequence, l, j) && check(sequence, j + 1, r - 1);
    }
}