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

题目描述

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

解题思路

• 无

AC代码

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        
        if(sequence.size() <= 0)
            return false;

        if(sequence.size() <= 1)
            return true;

        int root = sequence.back();
        vector<int>::iterator iter = sequence.begin();

        for(;iter != sequence.end() && *iter < root; iter++);
        for(;iter != sequence.end() - 1 && *iter > root; iter++);

        if(iter == sequence.end() - 1)
            return VerifySquenceOfBST(std::vector<int>(sequence.begin(), iter)) && 
                   VerifySquenceOfBST(std::vector<int>(iter, sequence.end()));

        return false;

    }
};