目录
刷题日期：19:4420 星期五2021年4月9日
个人刷题记录，代码收集，来源皆为leetcode
经过多方讨论和请教，现在打算往Java方向发力
主要答题语言为Java
题目：
剑指 Offer 33. 二叉搜索树的后序遍历序列
难度中等239
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000
题目分析
后序遍历即先查左子树，再查右子树，最后查根节点。
首先需要搞明白，某二叉树后序遍历搜索的结果有什么规律。输入数组不存在重复的数字。
难道还存在某个序列没有对应的二叉树吗，感觉题目中示例一也可以有自己的二叉树，比如
5
/ \
3 2
/ \
1 6
参考书，找到二叉树中，左子树节点的值都必须得比根节点的值小，而右子树则都比根节点的值大，那么上面第二层就不符合二叉树了。
初始解答：
因为是二叉树的题目，考虑递归
class Solution {
public boolean verifyPostorder(int[] postorder) {
//考虑特殊情况
if (postorder == null || postorder.length <= 0) return false;
//找到根节点的值
// int root = postorder[-1]; //不确定Java有没有这种写法
//左子树，小于根
for (int i = 0; i < postorder.length - 1; i++) {
if (postorder[i] > postorder[-1]) break;
}
int[] left = new int[i]; //新建前半截
int[] right = new int[postorder.length - i - 1]; //新建后半截
//定义左子树数组
for (int i = 0; i < postorder.length - 1; i++) left[i] = postorder[i];
//右子树，大于根
for (int j = i; j < postorder.length - 1; j++) {
right[j] = postorder[j];
if (postorder[i] < postorder[-1]) return false;
}
//递归左子树
boolean l = true;
if (i > 0) l = verifyPostorder(left);
//递归右子树
boolean r = true;
if (i < postorder.length - 1) r = verifyPostorder(right);
return l && r;
}
}
连最基本的数组定义都跑不过，还是放弃挣扎了。参考方法一
class Solution {
public boolean verifyPostorder(int[] postorder) {
//考虑特殊情况
if ( postorder.length <= 2) return true;
return bfs(postorder, 0, postorder.length - 1);
}
private boolean bfs (int[] postorder, int l, int r) {
if (l >= r) return true; //区域不合法返回true
//找到根节点的值
int root = postorder[r]; //不确定Java有没有这种写法
//左子树，小于根
int k = l;
while (k < r && postorder[k] < root) {
k++;
}
//右子树，大于根
for (int j = k; j < r; j++) {
if (postorder[j] < root) return false;
}
//递归左子树
if (!bfs(postorder, l, k - 1)) return false;
//递归右子树
if (!bfs(postorder, k, r - 1)) return false;
return true;
}
}
果然强，执行结果：通过
显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.7 MB, 在所有 Java 提交中击败了91.85%的用户
更简单的写法：
class Solution {
public boolean verifyPostorder(int[] postorder) {
return bfs(postorder, 0, postorder.length - 1);
}
private boolean bfs (int[] postorder, int l, int r) {
if (l >= r) return true; //区域不合法返回true
//左子树，小于根
int k = l;
while (postorder[k] < postorder[r]) k++;
//右子树，大于根
int m = k;
while (postorder[k] > postorder[r]) k++;
return k == r && bfs(postorder, l, m - 1) && bfs(postorder, m, r - 1);
}
}
执行结果：
通过
显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.9 MB, 在所有 Java 提交中击败了55.08%的用户
辅助栈：
class Solution {
public boolean verifyPostorder(int[] postorder) {
Deque<Integer> stack = new LinkedList<>(); //单调栈
int pervElem = Integer.MAX_VALUE;
//Integer.MAX_VALUE表示int数据类型的最大取值数：2 147 483 647
//翻转的先序遍历
for (int i = postorder.length - 1; i >= 0; i--) {
if (postorder[i] > pervElem) return false; //左子树元素要小与根
while (!stack.isEmpty() && postorder[i] < stack.peek()) pervElem = stack.pop();
//找到左子树对应的根节点
stack.push(postorder[i]); //这里用的是队列，栈的话就是add
}
return true;
}
}
空间可以理解，时间也变长了 执行结果：通过
显示详情
执行用时：1 ms, 在所有 Java 提交中击败了22.12%的用户
内存消耗：36 MB, 在所有 Java 提交中击败了29.64%的用户
学习他人：
方法一:
付有杰L2 2020-03-30 这个人的思路好强
class Solution {
// 要点：二叉搜索树中根节点的值大于左子树中的任何一个节点的值，小于右子树中任何一个节点的值，子树也是
public boolean verifyPostorder(int[] postorder) {
if (postorder.length < 2) return true;
return verify(postorder, 0, postorder.length - 1);
}
// 递归实现
private boolean verify(int[] postorder, int left, int right){
if (left >= right) return true; // 当前区域不合法的时候直接返回true就好
int rootValue = postorder[right]; // 当前树的根节点的值
int k = left;
while (k < right && postorder[k] < rootValue){ // 从当前区域找到第一个大于根节点的，说明后续区域数值都在右子树中
k++;
}
for (int i = k; i < right; i++){ // 进行判断后续的区域是否所有的值都是大于当前的根节点，如果出现小于的值就直接返回false
if (postorder[i] < rootValue) return false;
}
// 当前树没问题就检查左右子树
if (!verify(postorder, left, k - 1)) return false; // 检查左子树
if (!verify(postorder, k, right - 1)) return false; // 检查右子树
return true; // 最终都没问题就返回true
}
}
方法二：
失火的夏天L5 （编辑过）2020-02-14
看到蛮多大佬都用了递归来解决，这里提一个不一样的思路，单调栈。
二叉搜索树是left < root < right的，后序遍历的顺序是left->right->root，乍一看，好像没有办法保证单调性，不过我们可以做一个变化，后序遍历的逆序是什么呢？
root->right->left
发现什么了吗？是的，这是换了一个方向的先序遍历，从root开始，先遍历右子树，再遍历左子树。怎么做到先root，然后right，最后left呢，只要我们反向遍历数组，这样我们就可以利用单调栈了。
下面说说单调递增栈的思路和用法。
翻转先序遍历又是root->right->left的，基于这样的性质和遍历方式，我们知道越往右越大，这样，就可以构造一个单调递增的栈，来记录遍历的元素。
为什么要用单调栈呢，因为往右子树遍历的过程，value是越来越大的，一旦出现了value小于栈顶元素value的时候，就表示要开始进入左子树了（如果不是，就应该继续进入右子树，否则不满足二叉搜索树的定义，不理解的请看下二叉搜索树的定义），但是这个左子树是从哪个节点开始的呢？
单调栈帮我们记录了这些节点，只要栈顶元素还比当前节点大，就表示还是右子树，要移除，因为我们要找到这个左孩子节点直接连接的父节点，也就是找到这个子树的根，只要栈顶元素还大于当前节点，就要一直弹出，直到栈顶元素小于节点，或者栈为空。栈顶的上一个元素就是子树节点的根。
接下来，数组继续往前遍历，之后的左子树的每个节点，都要比子树的根要小，才能满足二叉搜索树，否则就不是二叉搜索树。
class Solution {
public boolean verifyPostorder(int[] postorder) {
// 单调栈使用，单调递增的单调栈
Deque<Integer> stack = new LinkedList<>();
int pervElem = Integer.MAX_VALUE;
// 逆向遍历，就是翻转的先序遍历
for (int i = postorder.length - 1;i>=0;i--){
// 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
if (postorder[i] > pervElem){
return false;
}
while (!stack.isEmpty() && postorder[i] < stack.peek()){
// 数组元素小于单调栈的元素了，表示往左子树走了，记录下上个根节点
// 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
pervElem = stack.pop();
}
// 这个新元素入栈
stack.push(postorder[i]);
}
return true;
}
}