code4offer-15 二叉搜索树的后序遍历序列

二叉搜索树的后序遍历序列

问题描述

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

分析

二叉搜索树的左子树 < 根节点， 右子树 > 根节点

判断是否是二叉搜索树的后序遍历序列可以看 序列是否能分为两段 前一段 < 根节点，后一段 > 根节点（也可能出现 只有左子树 或 只有 右子树的情况）

如果在大于根节点的元素后面出现了小于根节点的元素，则不是二叉搜索树的后序遍历序列

后序遍历（左右根）序列的最后一个元素为根节点的值，根据二叉搜索树的性质，可以从序列中分离出左子树和右子树，递归地对两个子树判断是否是二叉搜索树的后序遍历序列

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
26
public boolean Verify(int[] sequence, int left, int right) {
    if (left >= right) return true; // 无右子树时 left >= right
    int root = sequence[right];
    int i = left, j = 0;

    while (sequence[i] < root) ++i;
    j = i;
    while (j++ < right) {
        if (sequence[j] < root) {
            return false;
        }  
    }

    boolean leftV = Verify(sequence, left, i-1);
    boolean rightV = Verify(sequence, i, right-1);
    return leftV & rightV;
}


public boolean VerifySquenceOfBST(int [] sequence) {
    int len = sequence.length;
    if (len == 0) return false;
    if (len <= 2) return true;

    return Verify(sequence, 0, len - 1);
}