剑指Offer Java版 面试题33：二叉搜索树的后序遍历序列

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

练习地址

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

参考答案

public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return verify(sequence, 0, sequence.length - 1);
    }
    
    private boolean verify(int[] sequence, int start, int end) {
        // 子树为空
        if (start > end) {
            return true;
        }
        // 在二叉搜索树中左子树节点的值小于根节点的值
        int mid = start;
        while (mid < end && sequence[mid] < sequence[end]) {
            mid++;
        }
        // 在二叉搜索树中右子树节点的值大于根节点的值
        for (int i = mid + 1; i < end; i++) {
            if (sequence[i] < sequence[end]) {
                return false;
            }
        }
        // 判断左子树和右子树是不是二叉搜索树
        return verify(sequence, start, mid - 1) && verify(sequence, mid, end - 1);
    }
}

复杂度分析

• 时间复杂度：O(nlogn)。
• 空间复杂度：O(logn)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题