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

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目描述
输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

来源：https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=2&rp=4&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

剑指Offer 刷题二叉搜索树的后序遍历序列_子树

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0){
            return false;
        }
        return judge(sequence,0,sequence.length-1);
    }
    public boolean judge(int[] arr,int start,int end){
        if(start>=end){
        //说明此子树节点数量≤1 ，无需判别正确性，因此直接返回 true
               return true; 
        }
        
        int left = start;
        //在左子树中找到第一个比根结点大的结点
       while(arr[left]<arr[end]){
           left++;
       }
       //确定左右子树的分界线
        int right = left;
        while(arr[right]>arr[end]){
            right++;
        }
        //如果right能跑到end上，说明右子树比左子树大，则符合二叉搜索树的性质
        return right==end
            &&judge(arr,0,left-1)  //判断左子树
            &&judge(arr,left,right-1);  //判断右子树
    }
}

剑指Offer 刷题二叉搜索树的后序遍历序列_子树_02

剑指Offer 刷题二叉搜索树的后序遍历序列_Stack_03

剑指Offer 刷题二叉搜索树的后序遍历序列_数组_04

剑指Offer 刷题二叉搜索树的后序遍历序列_子树_05

import java.util.Stack;

public class Solution {
    public boolean VerifySquenceOfBST(int [] postorder) {
        if(postorder==null||postorder.length==0){
            return false;
        }
         Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;

    }
}