【剑指Offer】二叉搜索树的后序遍历序列

Posted on | In ,

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean VerifySquenceOfBST(int[] sequence) {
    if (sequence.length == 0)
        return false;

    return VerifySquenceOfBST(sequence, 0, sequence.length - 1);
}

private boolean VerifySquenceOfBST(int[] sequence, int start, int end){
    if (start >= end)
        return true;

    int idx = start;

    for (; idx < end; idx++){
        if (sequence[idx] > sequence[end])
            break;
    }

    for (int i = idx + 1; i < end; i++){
        if (sequence[i] < sequence[end])
            return false;
    }

    return VerifySquenceOfBST(sequence, start, idx - 1) && VerifySquenceOfBST(sequence, idx, end - 1);
}

相关题目

输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历的结果。这和前面问题的后序遍历很类似，只是在前序遍历得到的序列中，第一个数字是根结点的值。