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

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 j = r - 1;
        while(j >= l && sequence[j] > rootVal) j--;

        int m = j;

        // 验证剩余部分
        for(; j >= l; j--) {
            if(sequence[j] > rootVal) return false;
        }

        return check(sequence, l, m) && check(sequence, m + 1, r - 1);

    }
}