通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 33. 二叉搜索树的后序遍历序列

204人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/939

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

     5
    / \
   2   6
  / \
 1   3

示例 1:

输入: [1,6,3,2,5]
输出: false

示例 2:

输入: [1,3,2,6,5]
输出: true

提示:

 

  1. 数组长度 <= 1000

难度:中等;标签:无;编程语言:JAVA


我的解法

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorder(0, postorder.length - 1, Integer.MAX_VALUE+1l, postorder);
    }

    private boolean verifyPostorder(int start, int end, long p, int[] postorder){
        if(start >= 0 && end > start){
            int i = end - 1;
            while(i >= start){
                if(postorder[end] < postorder[i] && postorder[i] < p)i--;
                else if(postorder[i] >= p)return false;
                else break;
            }

            return verifyPostorder(start, i, postorder[end], postorder) && verifyPostorder(i + 1, end - 1, p,  postorder);
        }

        return true;
    }
}

自己写的一段时间自己又不会了,复习一下,中序是当前结点分成左右两部分,左边比当前小,右边比当前大,后序是当前结点分成左边两部分,左1比当前小,左2比当前大,据此,要有一个数进行比较,要分成两部分,从左到右,第一个大于最右(当前)结点的应该是左2的开始,左边是左1的结束,左1都小于当前结点,左2继续小于上一层结点


其它解法

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        int length = postorder.length;
        if(length == 0) {
            return true;    
        }
        
        return verifyPostorder(postorder, 0, postorder.length -1);
    }

    private boolean verifyPostorder(int[] postorder, int startIndex, int endIndex) {
        if(startIndex >= endIndex) {
            return true;
        }

        int value = postorder[endIndex];
        int rightIndex = startIndex;
        
        while(postorder[rightIndex] < value) {
            rightIndex++;
        }
        
        for(int i = rightIndex; i <= endIndex; i++) {
            if(postorder[i] < value) {
                return false;
            }
        }

        return verifyPostorder(postorder, startIndex, rightIndex -1) && verifyPostorder(postorder, rightIndex, endIndex -1);
    }
}

分成左1,左2两部分,左1比当前小,左2比当前大,然后左1,左2也是同样的情况


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告