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

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        return dfs(sequence, 0, sequence.length - 1);
    }
    boolean dfs(int[]sequence, int l, int r){
        if(l >= r) return true;
        int root = sequence[r];
        int right_child = r - 1;
        while(right_child >= 0 && sequence[right_child] > root) right_child --;
        //int left_child = 0;
        for(int left_child = l; left_child <= right_child; left_child ++){
            if(sequence[left_child] > root) return false;
        }
        return dfs(sequence, l, right_child) && dfs(sequence, right_child + 1, r - 1);
    }
}