题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
二叉搜索树：（若有）左子树全部结点小于根节点，（若有）右子树全部结点大于根节点。
因此若一个数组为二叉搜索树的后序遍历，则最后一个元素为根节点，前面的元素以某处分开前半部分全部小于此数，后半部分全部大于此数，且这两个部分又分别为一个二叉搜索树。
然而因为内存限制，不能直接递归调用给出的函数，而是新建一个有传值坐标的递归函数。
还要注意，二叉搜索树不能为空。
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if (sequence.size() == 0) return false; // 搜索树不能为空 return VerifySquenceOfBST(sequence, 0, sequence.size() - 1); } bool VerifySquenceOfBST(vector<int> sequence, int beginPos, int endPos) { // 由于空间限制重写一个具有pos传值的函数而不是直接递归调用原函数 if (endPos - beginPos <= 1) return true; int root = sequence[endPos]; int rightPos = beginPos; while (sequence[rightPos] < root) rightPos++; bool rightIsRight = true; for (int i = rightPos; i < endPos; i++) { if (sequence[i] < root) { rightIsRight = false; break; } } if (!rightIsRight) return false; return VerifySquenceOfBST(sequence, beginPos, rightPos - 1) && VerifySquenceOfBST(sequence, rightPos, endPos - 1); } };
原文：http://www.cnblogs.com/zmj97/p/7909079.html