作者：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也是同样的情况

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