判断数组是否为搜索二叉树的后序遍历
题目：
给一个整数型数组，在其中没有重复值的情况下，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则输出false,否则输出true
解法思路（递归）：
because 二叉树的后序遍历：左孩子—>右孩子—> 父结点
step1:如果一个数组arr是搜索二叉树的后序遍历结果，那arr的最后一个元素就是树的根结点root
step2:去掉最后一个元素arr[End]=root后, arr可以分成两段，(前一段 = 左子树）小于root，(后一段 = 右子树)大于root
step3: 分别递归前后两段，如果这（两段 = 子树）都是符合上述规则的。则输出true，否则输出false
例如：
input：arr = [2,4,6,5,3,7,10,9,8]
step1:根节点 root=8
step2:(前一段=左子树)：[2,4,6,5,3,7] (后一段=右子树)：[10，9]
step3: 前、后两段都符合规则
output：true
java实现：
public class verifySquenceOfBSTpostOrder {
public boolean solve(int[] arr){
if(arr == null || arr.length == 0){
return true;
}
return judge(arr,0,arr.length-1);
}
boolean judge(int[] arr, int Start, int End){
if(Start >= End){return true;}
//找到，根节点位置
int i = End ;
//找到左右子树临界位置
while (i > 0 && arr[i-1] > arr[End]){
--i;
}
//判断左边部分是不是都小于根节点
for( int j = i-1; j > 0; --j){
if(arr[j] > arr[End])
return false;
}
//分别递归左右子树
return judge(arr, Start, i-1) && judge(arr, i, End-1);
}
} public class verifySquenceOfBSTpostOrder { public boolean solve(int[] arr){ if(arr == null || arr.length == 0){ return true; } return judge(arr,0,arr.length-1); } boolean judge(int[] arr, int Start, int End){ if(Start >= End){return true;} //找到，根节点位置 int i = End ; //找到左右子树临界位置 while (i > 0 && arr[i-1] > arr[End]){ --i; } //判断左边部分是不是都小于根节点 for( int j = i-1; j > 0; --j){ if(arr[j] > arr[End]) return false; } //分别递归左右子树 return judge(arr, Start, i-1) && judge(arr, i, End-1); } }
