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

import java.util.*;

public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        // 处理空数组的情况
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return judge(sequence, 0, sequence.length - 1);
    }
    
    // 使用索引范围而不是复制数组，提高效率
    private boolean judge(int[] sequence, int start, int end) {
        // 递归出口：子树为空或只有一个节点
        if (start >= end) {
            return true;
        }
        
        int rootVal = sequence[end];  // 根节点值
        int leftEnd = start;  // 左子树结束位置
        
        // 找到第一个大于根节点的元素，划分左右子树
        while (sequence[leftEnd] < rootVal) {
            leftEnd++;
        }
        
        // 验证右子树所有元素都大于根节点
        for (int i = leftEnd; i < end; i++) {
            if (sequence[i] <= rootVal) {
                return false;  // 右子树存在小于等于根节点的值，不合法
            }
        }
        
        // 递归验证左右子树
        return judge(sequence, start, leftEnd - 1) &&  // 左子树
               judge(sequence, leftEnd, end - 1);      // 右子树
    }
}