二叉搜索树的后序遍历

题目表述

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

思路

二叉搜索树：空树、根节点大于左子树所有结点，根结点小于右子树所有结点。
后续遍历最后一个结点为根结点，从头遍历数组如果小于根结点则认为是左子树结点，找到第一个大于根结点数据的索引，开始遍历后面的数组，如果结点小于根结点直接return false。
再递归遍历...

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size()==0) {
            return false;
        }
        return VerifySquenceOfBST1(sequence,0, sequence.size()-1);
    }
    bool VerifySquenceOfBST1(vector<int>sequence,int start,int end) {
        if (start >= end) {
            return true;
        }
        //后续遍历最后一个结点为根结点
        int root = sequence[end];
        int num = 0;
        //判断左子树的结点是否小于根节点
        for (int i = 0; i <end; i++)
        {
            if (sequence[i] < root) {
                num++;
            }
            else
            {
                break;
            }
        }
        //判断左子树的结点是否大于根节点
        for (int j = num; j <end; j++)
        {
            if (sequence[j] < root) {
                return false;
            }
        }
        //判断左子树是否为二叉树               如：5，6，8，9，7
        bool left = true;
        if (num >start) {                     //5,6
            left = VerifySquenceOfBST1(sequence, start, num-1);
        }
        bool right = true;
        if (num < end) {                     //8,9
            right = VerifySquenceOfBST1(sequence, num,end-1);
        }
        return left&&right;
    }
};