二叉搜索树的后序遍历

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
分析：一棵二叉搜索树的后序遍历结果，必然是其中序遍历顺序入栈的其中一种出栈序列
实现：先对输入进行排序获取中序遍历结果，然后使用栈模拟遍历过程，最后栈为空，则后序遍历成立，代码如下：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) {
            return false;
        }

        vector<int> midSeq;
        midSeq.resize(sequence.size());
        copy(sequence.begin(), sequence.end(), midSeq.begin());
        sort(midSeq.begin(), midSeq.end());

        stack<int> s;
        for (int i = 0, r = 0; i <= midSeq.size(); ) {            
            if (!s.empty() && s.top() == sequence[r]) {
                s.pop();
                r++;
            }
            else if (i == midSeq.size()) {
                break;
            }
            else {
                s.push(midSeq[i]);
                i++;
            }
        }
        return s.empty();
    }
};