最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

剑指 Offer 33. 二叉搜索树的后序遍历序列(java解题)

来源:博客园


(相关资料图)

目录
  • 1. 题目
  • 2. 解题思路
  • 3. 数据类型功能函数总结
  • 4. java代码
  • 5. 踩坑小记
    • 递归调用,显示StackOverflowError

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的大小关系即可。
    • 如果右数组不符合要求,直接返回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;iroot_val){                    break;                }            }            //得到i,左右数组[start,i-1],[i,end-1]            //检查左右数组            int flag=0;            for(int j=i;j

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就会导致后序遍历一直停留在和根节点的比较上,无法退出循环,导致栈溢出。

关键词: