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

Posted on | In

问题描述

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

解题思路

找到二叉搜索树的根（遍历序列的最后一个元素），遍历序列的前一部分都比根小，后一部分都比根大。如果符合分别对前一部分和后一部分进行递归检验。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size()==0)return false;
        return check(sequence,0,sequence.size());
    }
    bool check(vector<int> &sequence, int s, int e) {
        if (s >= e) return true;
        int i = e;
        while (i > s && sequence[i - 1] > sequence[e]) i--;
        for (int j = i - 1; j >= s; j--) if (sequence[j] > sequence[e]) return false;
        return check(sequence, s, i - 1) && check(sequence, i, e - 1);
    }
};