好久没有写题了，之前看到这题是没什么思路，今天看了没一会儿就有思路了，哈哈。
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
我的思路
其实很简单的，搜索树后序，最后一个元素为根，前一部分比根小的元素为左子树，后一部分大的为右子树，递归下去保证不在两部分中发现大小不对的元素就可以了。
public class Solution {
public boolean VerifySquenceOfBST(int[] sequence) {
return sequence.length != 0 && isBST(0, sequence.length - 1, sequence);
}
private boolean isBST(int start, int end, int[] sequence) {
if (end - start < 2) {
return true;
}
int root = sequence[end];
int i = end - 1;
while (i >= start && sequence[i] > root) {
i--;
}
for (int j = i - 1; j >= start; j--) {
if (sequence[j] >= root) {
return false;
}
}
return isBST(start, i, sequence) && isBST(i + 1, end - 1, sequence);
}
}
其他方法
看到评论区有一种迭代的方法，思路其实和上面差不多，但是他每次大循环只消除数组最末尾一个元素。把前面数组看作一个新后序搜索树，新部分最后一个元素作为新根，把原来根的左子树看作是新根的左子树，因为一定比根小。但是访问次数其实是增多了。
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int size = sequence.size();
if(0==size)return false;
int i = 0;
while(--size)
{
while(sequence[i++]<sequence[size]);
while(sequence[i++]>sequence[size]);
if(i<size)return false;
i=0;
}
return true;
}
};
