题解 | #二叉搜索树的后序遍历序列#

/*
	简洁思路：
    后序遍历，每个区间都是最后一个为根节点
    比根节点小的都为左子树
    若右子树存在比根节点小的都不是空二叉搜索树
*/
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return false; // 空不为二叉搜索树
        int start = 0, end = sequence.size()-1; // 迭代判断的开始与结束序号
        return check(sequence, start, end);
    }

    bool check(vector<int> seq, int start, int end)
    {
        if (start >= end) return true;      // 若遍历到交叉点，那么都是满足条件

        // 寻找右子树
        int i = start;
        for(;i < end; ++i)
        {
            if(seq[i] > seq[end])   // 同时判断左子树都是小于根节点
            {
                break;
            }
        }
        int st = i-1;

        // 判断右子树都是大于根节点
        for(; i < end; ++i)
        {
            if(seq[i]< seq[end])
            {
                return false;
            }
        }

        // 判断迭代左子树
        bool left = check(seq, start, st);

        // 判断迭代右子树
        bool right = check(seq, st+1, end-1);

        // 综合判断
        return left&&right;
    }
};