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

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0) return false;
        //左右根
        //中序：左根右 也就是这个数组从小到大排序 
        int [] mid = Arrays.copyOf(sequence,sequence.length);
        Arrays.sort(mid);
        // 存不存在入栈顺序是mid 出栈顺序是后序的情况
        
        int n = mid.length;
        Stack<Integer>st = new Stack<Integer>();
        int i = 0, j = 0; //i指向入栈序列 j表示匹配成功出栈的数量
        while(i<n){
            st.add(mid[i]); //入栈
            while(!st.isEmpty() && st.peek().equals(sequence[j])){
                j++; //匹配上了
                st.pop();
            }
            i++;
        }
        return j==n;
    }
    
}

解题思路： 给出入栈队列 判断出栈队列是否合法

https://blog.nowcoder.net/n/50f7f77ddcd14a1d868194130a423cab