题目链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
1. 题目介绍（33. 二叉搜索树的后序遍历序列）
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
【测试用例】：
示例1：
输入: [1,6,3,2,5]
输出: false
示例2：
输入: [1,3,2,6,5]
输出: true
【条件约束】：
提示：
- 数组长度 <= 1000
【相关题目】：
输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历结果。这和前面问题的后序遍历很类似，只是在前序遍历得到的序列中，第一个数字是根节点的值。
【举一反三】：
如果面试题要求处理一棵二叉树的遍历序列，则可以先找到二叉树的根节点，再基于根节点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。本面试题应用的就是这种思路，面试题 7 ”重建二叉树“ 应用的也是这种思路。
2. 题解
2.1 递归（原书题解）-- O(nlogn)
时间复杂度O(nlogn)，空间复杂度O(n)
【解题思路】：
二叉搜索树：左子节点 < 根节点；右子节点 > 根节点
后序遍历：左、右、根，即，最后一个节点肯定是根节点
结合两者：数组中的数字就可以分为两部分；第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。
……
【实现策略】：（递归）
由于后序遍历的原因，所以我们很容易就能确定根节点值（rootVal）（即，数组的最后一个元素）。通过根节点与数组元素的依次比较，结合二叉搜索树的性质，将左右子树区域通过索引下标i来进行区分。然后经过判断以后，将左、右子树区域数组放入递归，用同样的方法确定其对应子树的结构。如果在递归的过程中，出现右子树区域有小于rootVal的情况，则结束递归，返回false（递归终止条件）.
class Solution {
// 二叉搜索树：左子节点 < 根节点；右子节点 > 根节点
// 后序遍历：左、右、根，即，最后一个节点肯定是根节点
// 结合两者：数组中的数字就可以分为两部分；
// 第一部分是左子树节点的值，它们都比根节点的值小；
// 第二部分是右子树节点的值，它们都比根节点的值大。
public boolean verifyPostorder(int[] postorder) {
// 判空
if (postorder.length <= 0) return true;
// 定义变量len，用来记录数组长度
int len = postorder.length;
// 定义变量rootVal，用来记录根节点值
int rootVal = postorder[len-1];
// 从头开始比较数组值与rootVal，划分左右子树区域
// 1. 划分左子树区域，遇到比根节点大的值时跳出循环
// 定义变量i，记录左子树区域索引
int i = 0;
for (;i < len-1; i++){
if (rootVal < postorder[i]) break;
}
// 2. 划分右子树区域
// 定义变量j，记录右子树区域索引
int j = i;
for (; j < len-1; j++){
if (rootVal > postorder[j]) return false;
}
// 判断左、右子树是不是二叉搜索树
// 左子树:
boolean left = true;
// i大于0，说明左子树存在
if (i > 0) {
// 1. 创建一个int数组，用来存储左子树区域值
int[] leftTree = new int[i];
// 2. 截取原数组
System.arraycopy(postorder,0,leftTree,0,Math.min(postorder.length,i));
// 3. 送入递归
left = verifyPostorder(leftTree);
}
// 右子树:
boolean right = true;
if (i < len-1) {
// 1. 创建一个int数组，用来存储右子树区域值
int[] rightTree = new int[len-i-1];
// 2. 截取原数组
System.arraycopy(postorder,i,rightTree,0,Math.min(postorder.length,len-i-1));
// 3. 送入递归
right = verifyPostorder(rightTree);
}
return (left & right);
}
}
【注意点】：
- 数组判空，要返回
true.
- 截取原数组的方法（
arraycopy()）
目标数组 = System.arraycopy(原数组, 原数组起始下标, 目标数组, 目标数组起始下标, 截取长度)
更多内容可参考：Java中数组的截取和查找检索
- 代码简化：
根据二叉搜索树的定义，可以通过递归，判断所有子树的 正确性 （即其后序遍历是否满足二叉搜索树的定义） ，若所有子树都正确，则此序列为二叉搜索树的后序遍历。
……
该题解的 优点 就在于，它通过新建的recur方法巧妙的避开了截取原数组，重新递归原方法的过程，而转变为通过定义首、中、尾三个索引下标来确定左右子树区域在原数组中的位置。
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
boolean recur(int[] postorder, int i, int j) {
if(i >= j) return true;
int p = i;
// postorder[j] ：表示根节点值
// 确定左子树区域
while(postorder[p] < postorder[j]) p++;
// 分隔点
int m = p;
// 确定右子树区域
while(postorder[p] > postorder[j]) p++;
// p = j ：表示来到了最后，是一个完整的遍历
return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
}
}
2.2 辅助单调栈 – O(n)
时间复杂度O(n)，空间复杂度O(n)
虽然该方法的理论时间复杂度为O(n)，但是其理解起来存在一定的难度，且实际效果表现不佳，因而还是推荐使用递归来解决此问题。
class Solution {
public boolean verifyPostorder(int[] postorder) {
Stack<Integer> stack = new Stack<>();
int root = Integer.MAX_VALUE;
for(int i = postorder.length - 1; i >= 0; i--) {
if(postorder[i] > root) return false;
while(!stack.isEmpty() && stack.peek() > postorder[i])
root = stack.pop();
stack.add(postorder[i]);
}
return true;
}
}
3. 参考资料
[1] 面试题33. 二叉搜索树的后序遍历序列（递归分治 / 单调栈，清晰图解）-- 图片 及 2.2 解法来源
