题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。解题思路：
在后序遍历得到的序列中， 最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分： 第一部分是左子树结点的值，它们都比根结点的值小： 第二部分是右子树结点的值，它们都比根结点的值大。
代码实现：{/*** 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。* 如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。** @param sequence 某二叉搜索树的后序遍历的结果* @return true：该数组是某二叉搜索树的后序遍历的结果。false：不是*/(int[] sequence) {// 输入的数组不能为空，并且有数据if (sequence == null || sequence.length <= 0) {return false;}// 有数据，就调用辅助方法return verifySequenceOfBST(sequence, 0, sequence.length – 1);}/*** 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。* 【此方法与上一个方法不同，未进行空值判断，，对于数组度为0的情况返回的true也于上题不同，* 此方法只是上面一个方法的辅助实现，对于数数组为null和数组长度为0的情况，执行结果并非相同】* 【也就是说此方法只有数组中有数据的情况下才与上面的方法返回同样的结点，* verifySequenceOfBST(sequence) ===* verifySequenceOfBST(sequence, 0, sequence.length – 1)* 当sequence中有数据才成立* 】** @param sequence 某二叉搜索树的后序遍历的结果* @param start 处理的开始位置* @param end处理的结束位置* @return true：该数组是某二叉搜索树的后序遍历的结果。false：不是*/(int[] sequence, int start, int end) {// 如果对应要处理的数据只有一个或者已经没有数据要处理（start>end）就返回trueif (start >= end) {return true;}// 从左向右找第一个不大于根结点（sequence[end]）的元素的位置int index = start;while (index < end – 1 && sequence[index] < sequence[end]) {index++;}right = index;(index < end – 1 && sequence[index] > sequence[end]) {index++;}(index != end – 1) {return false;}index = right;return verifySequenceOfBST(sequence, start, index – 1) && verifySequenceOfBST(sequence, index, end – 1);}(String[] args) {[] data = {4, 8, 6, 12, 16, 14, 10};System.out.println(“true: ” + verifySequenceOfBST(data));[] data2 = {4, 6, 7, 5};System.out.println(“true: ” + verifySequenceOfBST(data2));[] data3 = {1, 2, 3, 4, 5};System.out.println(“true: ” + verifySequenceOfBST(data3));[] data4 = {5, 4, 3, 2, 1};System.out.println(“true: ” + verifySequenceOfBST(data4));// 树中只有1个结点int[] data5 = {5};System.out.println(“true: ” + verifySequenceOfBST(data5));int[] data6 = {7, 4, 6, 5};System.out.println(“false: ” + verifySequenceOfBST(data6));int[] data7 = {4, 6, 12, 8, 16, 14, 10};System.out.println(“false: ” + verifySequenceOfBST(data7));}}运行结果：
题目扩展：
如果面试题是要求处理一棵二又树的遍历序列，我们可以先找到二叉树的根结点，再基于根结点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列．
有了你，我不再作孤飞于蓝天的雄鹰，
