LeetCode刷题【剑指 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

题解

以一个正确的序列为例，根据后续遍历的性质

1,3,2,6,5

应该是根节点，从根节点往前。比他大的部分应该为根节点的右子树，比根节点的小的应该是左子树，这样找到了[1,3,2]和[6]两个区间。而[6]只有一个节点，可以不做更多判断了。左边的[1,3,2]区间中，2必然是根节点，按照之前的方法，[1]是2的左子树上的节点，[3]是2的右子树上的节点。

在这样的分割的中还需要满足一个特征，就是比根节点小的部分和比根节点大的部分的应当是正好分割的，不能有重叠，也不能有中间空的部分。

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return validate(postorder,0,postorder.length-1);
    }


    private boolean validate(int[] postorder, int left ,int right){
        //如果左指针大于等于右指针了，说明当前节点以及没有子节点了，自然是符合条件的】
        //小于0的判断是从下面leftEnd rightStart 的初始赋值来的，说明没有这个子节点
        if (left>=right || left < 0 || right < 0) return true;
        //找到这段数组对应的根节点，根据后序遍历的特性，即为这段数组的最后一位
        int rootNum = postorder[right];
        //初始赋值
        int leftEnd = -1;
        int rightStart = -1;
        //开始遍历
        for (int i = left; i < right; i++) {
            if (postorder[i] < rootNum){
                //如果这个值小于根节点的值，说明这个节点应该是在左子树中
                leftEnd = i;
            }
            if (postorder[i] > rootNum && rightStart == -1){
                //如果这个值大于根节点的值，说明这个节点应该是右子树上的
                //且rightStart == -1 表示是第一次碰到的
                rightStart = i;
            }
        }
        //此时如果符合条件的话，应该是 leftEnd 在 rightStart 的左边一位
        //或者  没有左子树：leftEnd == -1 且rightStart == left
        //或者  没有右子树：rightStart == -1 且leftEnd == right-1
        boolean validateResult = (leftEnd>-1 &&  rightStart> -1 && leftEnd+1== rightStart)
                || ( leftEnd == -1 && rightStart == left )
                || ( rightStart == -1 && leftEnd == right-1);
        //自身验证完了，还要对分割好了的子序列的有效性判断
        if (validateResult){
            return validate( postorder, left, leftEnd ) && validate( postorder, rightStart, right-1 );
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)