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

    /// 递归解法
    /// </summary>
    /// <param name="sequence"></param>
    /// <returns></returns>
    bool VerifySquenceOfBST(vector<int> sequence)
    {
        if (sequence.size() == 0)
            return false;
        if (sequence.size() == 1)
            return true;
        // 取根节点
        int root_val = sequence[sequence.size() - 1];
        vector<int> left_v;
        vector<int> right_v;
        int index = 0;
        bool over = false;
        for (int i = 0; i < sequence.size() - 1; i++)
        {
            // 前面的一定要小于root
            // 后面的一定要大于root
            if (sequence[i] < root_val)
            {
                left_v.push_back(sequence[i]);
                if (i > index && over)
                    return false;
            }
            else
            {
                right_v.push_back(sequence[i]);
                index = i;
                over = true;
            }
        }
        bool left = left_v.size() > 0 ? VerifySquenceOfBST(left_v) : true;
        bool right = right_v.size() > 0 ? VerifySquenceOfBST(right_v) : true;
        return left && right;
    }