题解 | #二叉搜索树的后序遍历序列#

package com.yzc.offer.JZ33;

import java.time.temporal.ValueRange;
import java.util.Currency;

/**
 * @author YZC
 * @Date 2021/12/5/12:16
 */

public class Solution {
    /*
    * 后序遍历 根节点一定是在最后一位
       找到第一个 比根节点大的位置m
    那么 左子树区域 就是 i->m-1 右子树 区域 就是 m->j-1
    *
    * */
    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[] arr = {1, 3,2};
        int[] arr = {1,6,5,3};
        boolean b = solution.VerifySquenceOfBST(arr);
        System.out.println(b);

    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)
            return false;
        return judge(sequence,0,sequence.length-1);
    }
    boolean judge(int[] arr,int start,int end){
//        if((start-end)>=-1)
        if(start>=end)
            return true;
        int i=start;
        //找出左子树范围
        while(i<end&&arr[i]<arr[end])
            i++;
        int mid=i;
        //找出右子树范围
        while(i<end&&arr[i]>arr[end])
            i++;
        return i==end&&judge(arr,start,i-1)&&judge(arr,i,end-1);
    }
}


   /* 2 public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        int n = sequence.length;
        return recur(sequence, 0, n - 1);
    }

    public boolean recur(int[] nums, int i, int j) {
        if (i >= j) {
            return true;
        }
        int p = i;
        while (nums[p] < nums[j]) p++;
        int m = p;
        while (nums[p] > nums[j]) p++;
        return p == j && (recur(nums, i, m - 1)) && recur(nums, m, j - 1);

    }
}*/


/*
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {10,2,6};
        boolean b = solution.VerifySquenceOfBST(arr);
        System.out.println(b);

    }

    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return verify(sequence, 0, sequence.length - 1);
    }


    public boolean verify(int[] sequence, int first, int last) {

        if (last - first <= 1) {
            return true;
        }
        int rootval = sequence[last];
        int cutIndex = first;
        while (cutIndex < last && sequence[cutIndex] <= rootval) {
            cutIndex++;
        }

        for (int i = cutIndex; i < last; i++) {
            if (sequence[i] < rootval) {
                return false;
            }
        }

        return verify(sequence, first, cutIndex - 1) && verify(sequence, cutIndex, last -1);

    }


}
*/