PS：《剑指offer》是很多同学找工作都会参考的一本面试指南，同时也是一本算法指南（为什么它这么受欢迎，主要应该是其提供了一个循序渐进的优化解法，这点我觉得十分友好）。现在很多互联网的算法面试题基本上可以在这里找到影子，为了以后方便参考与回顾，现将书中例题用Java实现（第二版），欢迎各位同学一起交流进步。
GitHub： https://github.com/Uplpw/SwordOffer。
完整题目链接： https://blog.****.net/qq_41866626/article/details/120415258
目录
1 题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
例子：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
leetcode链接： 二叉搜索树的后序遍历（以下代码已测试，提交通过）
2 测试用例
一般是考虑功能用例，特殊（边缘）用例或者是反例，无效测试用例这三种情况。甚至可以从测试用例寻找一些规律解决问题，同时也可以让我们的程序更加完整鲁棒。
（1）功能用例：完全与非完全二叉树。
（2）边缘用例：只有一个节点，只有左节点，只有右节点。
（3）无效用例：树为空。
3 思路
分析：
注意：题目包含两个信息：二叉搜索树、后序遍历
二叉搜索树的特点：左子树比父节点都小，右子树比父节点都大。
后序遍历：左——右——根
因此，有以下过程：
（1） 比根结点小的值都在根结点的左子树上，一旦有大于根结点的值出现，说明左子树已经遍历完。
（2） 找到第一个大于根结点的值，这个值就是后序遍历右子树的第一个点。
（3） 从第2步找到的点开始遍历完剩下的所有结点，如果在这期间发现有比根结点小的值，说明不是BST（二叉搜索树）。
（4） 左子树和右子树递归执行前三步。
4 代码
算法实现：
public class verifySquenceOfBST {
public static boolean verifyPostorder(int[] postorder) {
return verifyPostorderCore(postorder, 0, postorder.length - 1);
}
public static boolean verifyPostorderCore(int[] postorder, int start, int end) {
if (start >= end) return true;
int temp = start;
// 找到右子树结点第一次出现的地方。（或者说是遍历完整棵左子树）
for (int i = start; i <= end; ++i) {
if (postorder[i] < postorder[end]) {
temp = i;
} else break;
}
// 后序遍历右子树时会访问的第一个结点的下标。
int rightTreeNode = temp + 1;
// 验证右子树所有结点是否都大于根结点。
for (int i = rightTreeNode; i < end; ++i) {
if (postorder[i] > postorder[end]){
++rightTreeNode;
}else {
return false;
}
}
// 注意左右子树开始结束索引位置
return verifyPostorderCore(postorder, start, temp) && verifyPostorderCore(postorder, temp + 1, end - 1);
}
public static void main(String[] args) {
// 8
// / \
// 6 10
// / \ / \
// 5 7 9 11
int[] data = {5, 7, 6, 9, 4, 10, 8};
int[] data1 = {5, 7, 6, 9, 11, 10, 8};
System.out.println(verifyPostorder(data));
System.out.println(verifyPostorder(data1));
}
}
参考
在解决本书例题时，参考了一些大佬的题解，比如leetcode上的官方、K神，以及其他的博客，在之后的每个例题详解后都会给出参考的思路或者代码链接，同学们都可以点进去看看！
本例题参考：
https://www.jianshu.com/p/49aaf6e0491d
本文如有什么不足或不对的地方，欢迎大家批评指正，最后希望能和大家一起交流进步、拿到心仪的 offer !!!