1. 题目
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/ \
2 6
/ \
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
提示:
数组长度 <= 1000
作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vwxx5/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
2. 解题思路
使用递归分治的思路:
- 根据最后一个值
x
,划分为左右子数组;- 查找比x大的元素,第一个比x大的元素下标为
i
,在此处划分数组[start,i-1]
和[i,end]
;
- 查找比x大的元素,第一个比x大的元素下标为
- 检查左右数组:左数组的元素均小于
x
,右数组的元素均大于x
。- 由于左数组元素和
x
的大小关系已经确定,只需要检查右数组和x
的大小关系即可。 - 如果右数组不符合要求,直接返回
false
;否则继续执行下一步
- 由于左数组元素和
- 对左右子数组,重复上述步骤;
终止条件:数组为空或者只有一个元素,返回true
3. 数据类型功能函数总结
//数组
int len=arrayname.length;//数组长度
4. java代码
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder,0,postorder.length-1);
}
public boolean recur(int[] postorder,int start,int end){
if(end-start<=1){
return true;
}
else{
int root_val=postorder[end];
int i=start;
for(i=start;i<end;i++){
if(postorder[i]>root_val){
break;
}
}
//得到i,左右数组[start,i-1],[i,end-1]
//检查左右数组
int flag=0;
for(int j=i;j<end && flag==0;j++){
if(postorder[j]<root_val){
flag=1;
}
}
if(flag==0){
return recur(postorder,start,i-1)&&recur(postorder,i,end-1);
}
else{
return false;
}
}
}
}
5. 踩坑小记
递归调用,显示StackOverflowError
递归函数的部分为:
if(flag==0){
return recur(postorder,start,i-1)&&recur(postorder,i,end-1);
}
而我一开始写成了:
if(flag==0){
return recur(postorder,start,i-1)&&recur(postorder,i,end);
}
然后一直报错显示StackOverflowError
,后来发现是右数组划分的时候,传入end
就会导致后序遍历一直停留在和根节点的比较上,无法退出循环,导致栈溢出。
原文链接:https://www.cnblogs.com/CrazyPixel/p/17344317.html
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:剑指 Offer 33. 二叉搜索树的后序遍历序列(java解题) - Python技术站