【问题】输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
【思路】注意题目给出的是二叉搜索树，那么它就有一个很重要的性质：左孩子值<=根的值<=右孩子的值！但题目中说明了任意两个数字都互不相同，说明没有重复数字。
由于给出的是后序遍历，我们就可以知道最后一个数为根节点，并且其左子树的值均小于根节点的值，右子树的值均大于根节点的值。因此我们可以从头遍历，直到找到第一个大于根节点的值，我们就可以得到左右子树划分的边界，其后面所有值都应该大于根节点的值，最后利用分治思想进行递归即可！
class Solution { public: bool process(vector<int> seq, int start, int end){ if(seq.size() == 0) return false; int i; // 左子树的索引 if (start >= end){ return true; } for(i = 0;i < end; i++){ if(seq[i] > seq[end]){ break; } } for(int j = i;j < end; j++){ // j 为右子树的索引 if(seq[j] < seq[end]){ return false; } } return process(seq, start, i-1) && process(seq, i, end-1); } bool VerifySquenceOfBST(vector<int> sequence) { if (sequence.size() == 0) return false; if (sequence.size() == 1) return true; return process(sequence, 0, sequence.size()); } };
原文：https://www.cnblogs.com/zhudingtop/p/11337938.html