LeetCode刷题【剑指 Offer 33】二叉搜索树的后序遍历序列

     5
    / \
   2   6
  / \
 1   3

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

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

分段验证

解题思路

分段验证

代码

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


    private boolean validate(int[] postorder, int left ,int right){
        //如果左指针大于等于右指针了，说明当前节点以及没有子节点了，自然是符合条件的】
        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;
    }
}