20190317二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
满二叉树：从高到低，除了叶结点外，所有结点的左右结点都存在。
完全二叉树：比满二叉树少几个叶结点，从左向右放子结点。
平衡二叉树：空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。、
二叉搜索树：空树或者二叉树的所有结点比它的左子结点大，比它的右子结点小。
例如输入数组{5， 7， 6， 9， 11， 10， 8}，则返回true，因为这个整数序列是上图二叉搜索树的后序遍历结果。如果输入的数组是{7， 4， 6， 5}，由于没有哪颗二叉搜索树的后序遍历的结果是这个序列，因此返回false。
在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。
以数组{5， 7， 6， 9， 11， 10， 8}为例，后序遍历的结果中最后一个值8就是根结点，在这个数组中前3个数字5，7， 6都比8小是根结点8的左子树结点；后3个数字9， 11， 10都比8大，是根结点8的右子树结点。
接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个递归的过程。对于序列5， 7， 6的子树而言，6是根结点，5是根结点6的左子结点，7是根结点6的右子结点；同样对于序列9， 11， 10的子树而言，10是根结点，9是根结点10的左子结点，11是根结点10的右子结点。
以数组{7， 4， 6， 5}为例，后序遍历的结果中最后一个值5就是根结点。数组的第一个数字7大于5，故此二叉搜索树没有左子树， 7， 4， 6都是右子树结点的值。我们发现4比5小，违背了二叉搜索树的规定。故此数组不是二叉搜索树的后序遍历。
代码实现
import java.util.Arrays;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
int len = sequence.length;
if(len<=0){
//这个是针对第一次数组是否为空的判断，后面是通过i和j的位置来判断数组不为空
return false;
}
int i = 0;
int root = sequence[len-1];
for(;i<len-1;i++){
if(root<sequence[i])
break;
}
int j = i;
for(;j<len-1;j++){
if(root>sequence[j]){
return false;
}
}
boolean judgeLeftTree = true;
boolean judgeRightTree = true;
if(i>0){
judgeLeftTree = VerifySquenceOfBST(Arrays.copyOfRange(sequence,0,i));
}
if(j<len-1){
judgeRightTree = VerifySquenceOfBST(Arrays.copyOfRange(sequence,j,len-1));
}
return judgeLeftTree&&judgeRightTree;
}
}【参考】