二叉搜索树的后续遍历

题目描述：

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

解题思路：

1. 根据后续遍历的特点，每次遍历到根结点的时候都是最后一位
2. 而二叉搜索树的特点就是左子树都小于等于root，右子树都大于等于root
3. 所以，先找到根结点，然后由前向后遍历该序列
4. 开始的部分的数值应该都是小于等于root的（左子树），当某个结点大于root的值的时候，此结点开始就是右子树
5. 遍历右子树的所有数值（后序遍历的中后段），如果有数值小于root，则说明该序列不是后续遍历序列
6. 递归地判断做子树和右子树，如果左右子树也都是满足后续遍历的特点，那么整个序列就都满足后续遍历的特点。

代码：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) {
            return false;
        }
        int length = sequence.size();
        int root = sequence[length - 1];

        // 从前向后遍历sequence序列
        int i = 0;
        for (; i < length - 1; ++i) {
            if (sequence[i] > root) 
                break;
        }

        // 用另外一个变量来记录右子树开始的地方
        int j = i;
        // 遍历右子树，如果右子树中有元素小于root，则返回false
        for (; j < length - 1; j++) {
            if (sequence[j] < root) {
                return false;
            }
        }

        bool left = true;
        bool right = true;
        vector<int> leftSeq, rightSeq;
        for (int count = 0; count < i; ++count) {
            leftSeq.push_back(sequence[count]);
        }
        for (int count = i; count < length - 1; ++count) {
            rightSeq.push_back(sequence[count]);
        }

        // 如果左子树不是空树，即左子树的结尾结点大于0
        // 递归验证左半子树
        if (i > 0) {
            left = VerifySquenceOfBST(leftSeq);
        }
        // 如果右子树不是空树
        // 递归验证右半子树
        if (i < length - 1) {
            right = VerifySquenceOfBST(rightSeq);
        }

        return left && right;
    }
};

2018.10.12