题目链接
牛客在线oj题——二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
数据范围： 节点数量 0≤n≤1000 ，
节点上的值满足1≤val≤10^5 ，保证节点上的值各不相同
要求：空间复杂度 O(n) ，时间时间复杂度 O(n^2 )
提示：
- 二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
- 该题我们约定空树不是二叉搜索树
- 后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
- 参考下面的二叉搜索树，示例 1
题目示例
示例1
输入：
[1,3,2]
返回值：
true
说明：
是上图的后序遍历 ，返回true
示例2
输入：
[3,1,2]
返回值：
false
说明：
不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false
示例3
输入：
[5,7,6,9,11,10,8]
返回值：
true
解题思路
二叉搜索树的特点是父亲节点大于左子树所有节点的值，小于右子树所有节点的值
而后序遍历则是先遍历左子树，再遍历右子树，然后输出父节点的值
定义数组的第一个元素下标为start，最后一个元素下标为end。
首先拿到数组中最后一个节点end下标对应的的值，这个值就是父节点的值，然后从左到右遍历数组，当遇到比父节点的值更大的元素停止，这个节点下标为i
可以确定[start, i - 1]为当前遍历序列的左子树序列，而[i, end - 1]则是当前遍历序列的右子树序列
继续遍历[i, end - 1]序列，如果有元素小于父节点的值，说明这个序列不满足二叉搜索树的性质，返回false
需要注意的是，当前只是确定了当前序列是否满足二叉搜索树的性质，而我们需要判断所有的子树是否都满足二叉搜索树的性质，也就是说上述过程我们分别要对[start, i - 1]序列和[i, end - 1]序列分别再次验证
因此，可以通过递归来验证，最后的终止条件是：当start <= end时，返回true
完整代码
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0){
return false;
}
int start = 0;
int end = sequence.length - 1;
return VerifySquenceOfBSTHelper(sequence, start, end);
}
private boolean VerifySquenceOfBSTHelper(int[] sequence, int start, int end) {
if(start >= end){
return true;
}
int root = sequence[end];
int i = start;
while(i < end && sequence[i] < root){
i++;
}
for(int j = i; j < end; j++){
if(sequence[j] < root){
return false;
}
}
return VerifySquenceOfBSTHelper(sequence, start, i - 1) && VerifySquenceOfBSTHelper(sequence, i, end - 1);
}
}
