题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出 No 。假设输入的数组的任意两个数字都互不相同。
思路分析
这道题的关键点是「二叉搜索树」和「后续遍历」，二叉搜索树有个特点，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
简单的说，左子树节点的值 < 根 < 右子树节点的值；后序遍历特点是「左右根」顺序，所以后序遍历的根是在最后一个；
举个例子：
二叉树
判断该数组序列 [1, 7, 5, 9, 11, 10, 8 ] 是否符合图纸二叉树的后续遍历。
其中 8 是根节点，[1, 7, 5] 比 8 小，是左子树；[9, 11, 10] 比 8 大，是右子树；
然后又是熟悉的递归了，我们继续判断，左子树 [1, 7, 5] 是否是二叉树搜索树，其中 5 是根节点，1 < 5 是左子树， 7 > 5 是右子树；
判断，右子树 [9, 11, 10] 是否是二叉树搜索树，其中 10 是根节点， 9 < 10 是左子树，11 > 10 是右子树；
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length <= 0 || sequence == null){
return false;
}
return isBSTLastOrder(sequence, 0, sequence.length - 1);
}
private boolean isBSTLastOrder(int [] sequence, int start, int end){
// 边界条件
if(start > end){
return true;
}
//根节点
int root = sequence[end];
int i = start;
// 划分左右子树，并判断左右子树和根节点的关系
while(sequence[i]< root){
i++;
}
int j=i;
while(j < end){
if(sequence[j]< root){
return false;
}
j++;
}
boolean left = isBSTLastOrder(sequence, start, i-1);
boolean right = isBSTLastOrder(sequence, i, end-1);
return left&&right;
}
}
参考文献：
https://blog.csdn.net/Heloiselt/article/details/80227473
