题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
常规做法随便在网上搜就有，我在讨论区中看到一位大佬提供了新的思路：对于一颗二叉搜索树，它的中序遍历序列就是有序的，比如这个图，中序遍历是1,2，3，后序遍历是1,3,2，根据我之前写过一个题目是“栈的压入、弹出序列”https://blog.csdn.net/BBF_Sherry/article/details/108369343，可以发现一颗二叉搜索树的中序遍历和后序遍历是满足这个题目的，即可以把中序遍历序列看做压入序列，把后续遍历序列看做弹出序列，当题目中给出的序列满足弹栈时，就说明该序列是二叉搜索树的后序遍历序列。代码如下：
public boolean VerifySquenceOfBST(int[] sequence) { if (sequence == null || sequence.length == 0) { return false; } int[] arr = sequence.clone(); Arrays.sort(arr); return IsPopOrder(arr, sequence); } private boolean IsPopOrder(int[] pushA, int[] popA) { if (pushA == null || popA == null) { return false; } Stack<Integer> stack = new Stack<>(); int index = 0; for (int i = 0; i < pushA.length; i++) { stack.push(pushA[i]); while (!stack.isEmpty() && stack.peek() == popA[index]) { stack.pop(); index++; } } return stack.isEmpty(); }在牛客网和力扣上面都是可以通过的。
之前在这里我有个疑问，中序遍历的弹栈序列有很多种，后序遍历序列只是其中一种，是必要不充分的条件，假如题目提供一个int[] arr = { 1,2,3 }，这显然不是一个后序遍历序列，但是它却满足弹栈要求所以输出也为true，所以说这个方法是不正确的吗？但是其实1,2,3也是一个后序遍历序列，有时候真是不能想当然啊。
