题目

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

思路

思想很简单，后序遍历的最后一个数字是根节点，检查根节点是不是比左子树都要大，比右子树都要小。

接着把序列分成两半，递归检查左子树和右子树是否满足后序遍历。

class Solution {public:    bool VerifySquenceOfBST(vector
     
       sequence) {        if (sequence.size() == 0)            return false;        int length = sequence.size();        int root = sequence[length - 1];        int i = 0;        for (; i < length - 1; i++){            if (sequence[i] > root)                break;        }                int j = i;        for (; j < length - 1; j++){            if (sequence[j] < root)                return false;        }                bool left = true, right = true;        vector
      
        LeftTree, RightTree;        for (int m = 0; m < i; m++)            LeftTree.push_back(sequence[m]);        for (int m = i; m < length - 1; m++ )            RightTree.push_back(sequence[m]);        if (i > 0)            left = VerifySquenceOfBST(LeftTree);        if (i < length - 1)            right = VerifySquenceOfBST(RightTree);        return (left && right);    }};