33.二叉搜索树的后序遍历序列
面试题33. 二叉搜索树的后序遍历序列
难度中等39
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回
false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树：
5 / 2 6 / 1 3示例 1：
输入: [1,6,3,2,5] 输出: false示例 2：
输入: [1,3,2,6,5] 输出: true
1.递归-分治
时间复杂度:O(n^2) 每次调用 recur(i,j) 减去一个根节点，因此递归占用 O(N) ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N)
空间复杂度 O(N) ： 最差情况下（即当树退化为链表），递归深度将达到 NN 。
//递归 --分治
//后序遍历 左右根 特点左子树节点的值均小于根节点 右子树节点的值均大于根节点
//由此可知 数组中最后一个元素就是跟节点。通过两次for 找到第一个大于root.val的值
//将数组划分成 小于根节点的 和 大于根节点的 两部分，通过递归调用 就可以逐一比较。
public boolean verifyPostorder(int[] postorder) {
if(postorder == null || postorder.length == 0){
return true;
}
return verify(postorder,0,postorder.length-1);
}
public boolean verify(int [] postorder,int first,int last){
if(last-first<=1){ //如果数组中只有一个元素 说明是有序的。
return true;
}
int curIndex = first;
int rootVal = postorder[last];//根节点
//找到第一个大于根节点的值 下标
while(curIndex < last && postorder[curIndex]<=rootVal ){
curIndex++;
}
for(int i = curIndex;i<last;i++){
//如果右子节点小于根节点 不是BST
if(postorder[i]<rootVal){
return false;
}
}
return verify(postorder,first,curIndex-1) && verify(postorder,curIndex,last-1);
}