剑指Offer第23题：二叉搜索树的后序遍历序列

发表于 更新于 分类于

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

解题思路：二叉搜索树中，左子树的值小于根结点小于右子树。二叉搜索树的后序遍历中，根结点在最右边的位置，遍历数组，找到第一个大于根结点的值，则该值左边为左子树，包含该值的右边为右子树（去除根结点）；继续搜寻数组，若存在比根结点小的值，则该数组肯定不是二叉搜索树的后续遍历，直接返回false。递归判断左右子树是否为后序遍历的二叉搜索树即可。

代码：
法一：定义两个辅助数组，用于存放左右序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool VerifySquenceOfBST(vector<int> sequence) {
    if (sequence.empty()) return false; //先判断给出的序列是否为空
    vector<int> left_seq;
    vector<int> right_seq;
    int root_val = sequence.back();
    int i=0; //在for循环的外部定义i
    for (; i<sequence.size()-1; i++) {
        if (sequence[i] < root_val) left_seq.push_back(sequence[i]);
        else break;
    }
    for (; i<sequence.size()-1; i++) {
        if (sequence[i] < root_val) return false;
        right_seq.push_back(sequence[i]);
    }
    bool left = true;
    if (!left_seq.empty()) left = VerifySquenceOfBST(left_seq);
    bool right = true;
    if (!right_seq.empty()) right = VerifySquenceOfBST(right_seq);
    return left && right;
}

法二：不需要定义辅助数组，直接记录左右子树的起始位置和终止位置即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool VerifySquenceOfBSTHelper(vector<int> &seq, int start, int end) {
    if (seq.empty()) return false;
    if (start >= end) return true; // 等效于 if (start > end) {} else return true
    int root_val = seq.back();
    int i=0;
    for (; i<end; i++) {
        if (seq[i] > root_val) break;
    }
    for (int j=i; j<end; j++) 
        if (seq[j] < root_val) return false;
    return VerifySquenceOfBSTHelper(seq, 0, i-1) && VerifySquenceOfBSTHelper(seq, i, end-1);
}
bool VerifySquenceOfBST(vector<int> sequence) {
    return VerifySquenceOfBSTHelper(sequence, 0, sequence.size()-1);
}