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

import java.util.*; public class Solution { public boolean VerifySquenceOfBST(int [] sequence) {

 //全大于根节点  、、全小于根节点     先小于 再 大于
    //再开两个数组  存左和右  
    
    //最后一个是根节点    
    //小于根节点的全加到左数组
    //大于根节点的加到右数组    设置开关leftAdd 一旦右数组里添加元素，左数组不能再加，否则直接false
    //   判断   左数组&&右数组
    ArrayList<Integer> left = new ArrayList<>();
    ArrayList<Integer> right = new ArrayList<>();
    int len = sequence.length;
    if(len == 0) {
        return false;
    }
    if(len == 1) {
        return true;
    }
    int mid = sequence[len-1];
    boolean leftAdd = true;
    for(int i = 0; i< len- 1; i++) {
        if(sequence[i] < mid) {
            if(leftAdd) {
                left.add(sequence[i]);
            } else {
                return false;
            }
        } 
        if(sequence[i] > mid) {
            right.add(sequence[i]);
            leftAdd = false;
        }
    }
    
    // List转int操作
    

// System.out.println("int[] 类型对象：");

// int[] ints = new int[list.size()];

// for (int i = 0; i < list.size(); i++) {

// ints[i] = list.get(i);

// }

    int[] leftArr = new int[left.size()];
    for(int i= 0; i < left.size(); i++) {
        leftArr[i] = left.get(i);
    }
    int[] rightArr = new int[right.size()];
    for(int i=0; i<right.size(); i++) {
        rightArr[i] = right.get(i);
    }
    
    
    if(left.size()==0) {
        return VerifySquenceOfBST(rightArr);
    } else if(right.size() == 0) {
        return VerifySquenceOfBST(leftArr);
    } else {
        return VerifySquenceOfBST(leftArr) && VerifySquenceOfBST(rightArr);
    }
}

}