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

本文最后更新于：2022年4月9日 中午

image-20211008101854158

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0) return false;
        return verify(sequence, 0, sequence.size()-1);
    }
    bool verify(const vector<int> seq, int start, int end) {
        if (start >= end) return true;
        int rootVal = seq[end];
        int delim = 0;
        for (delim = start; delim < end; ++delim) {
            if (seq[delim] > rootVal) break;
        }
        // 判断右子树中是否有小于根结点的值
        for (int i = delim+1; i < end; ++i) {
            if (seq[i] < rootVal) return false;
        }
        return verify(seq, start, delim-1) && verify(seq, delim, end-1);
    }
};