🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🌳1. 包含min函数的栈
描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
编辑
解题思路：
🎈1. 思路一：看到题目时，我们可以简单的想到设置一个min变量储存最小值，每当入数据栈元素小于min时，更新min即可。
🎈2. 思路二：但是思路一我们只能得到数据栈中的最小值，假若面试官要求我们求数据栈中第二小值和第三小值，此方法就行不通了。因此我们可以设置一个辅助栈，辅助栈中的元素个数和数据栈个数相同，只是辅助栈每次存入的是当前已存入数据栈中的最小值，这样如果要求数据栈中第二小值，可以同时让数据栈data_stack和辅助栈min_stack先出栈一个元素，然后return min_stack.peek即可得到数据栈中第二小的值。
🍤思路二：代码如下：
import java.util.Stack; public class TwoStackIncludeMin_17 { // 数据栈（存入栈元素） Stack<Integer> data_stack = new Stack<>(); // 辅助栈（存入当前数据栈中元素最小值） Stack<Integer> min_stack = new Stack<>(); public void push(int node) { // 先将node存入数据栈 data_stack.push(node); // 判断辅助栈是否为空 if(min_stack.isEmpty()){ // 如果辅助栈为空，直接将node存入辅助栈 min_stack.push(node); }else { // 如果辅助栈不为空，先将node和辅助栈的栈顶元素做比较 // 将小的元素存入辅助栈 if(min_stack.peek() <= node){ // 辅助栈的栈顶元素更小 min_stack.push(min_stack.peek()); }else { // node 更小 min_stack.push(node); } } } public void pop() { // 数据栈和辅助栈同时出栈，保证两栈元素个数一致 data_stack.pop(); min_stack.pop(); } public int top() { return data_stack.peek(); } // 当期数据栈中最小元素就是辅助栈的栈顶元素 public int min() { return min_stack.peek(); } }
🌳2. 栈的压入、弹出序列
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
编辑
解题思路：
🎈1. 思路一：我们知道可以根据第二个序列也就是出栈顺序，能够得到指定的入栈顺序
（如例题中，第二个序列第一个数为4，入栈时肯定先入栈1，2，3，4，然后才能将4出栈；第二个序列第二个数为5，所以入栈时再将5入栈，然后才能将5出栈，继而将3出栈，2出栈，1出栈）
因此，我们可以遍历第一个序列和第二个序列，当第二个序列元素不等于入栈元素时，继续将第一个序列元素入栈；当第二个序列元素等于入栈元素时，弹出栈顶元素；
如此一直循环，当第一个序列元素全部入栈后，退出循环，判断此时栈是否为空，如果栈为空，说明第二个序列元素将栈中元素全部弹出，第二个序列就是是为该栈的弹出顺序。
🍤思路一：代码如下：
import java.util.Stack; public class IsPopOrder_18 { public boolean IsPopOrder(int [] pushA,int [] popA) { // 当第一序列或第二序列为空时，直接返回false if(pushA == null || popA == null || pushA.length ==0 || popA.length == 0){ return false; } Stack<Integer> stack = new Stack<>(); int i = 0; int j = 0; for (;i < pushA.length ; i++) { // 将第一序列元素入栈 stack.push(pushA[i]); // 当第二个序列元素等于入栈元素时，弹出栈顶元素 while (!stack.isEmpty() && stack.peek() == popA[j]){ stack.pop(); j++; } } // 如果符合要求，最后栈结构一定是空的 return stack.isEmpty(); } }
🌳3. 从上往下打印二叉树
描述
不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面。
编辑
解题思路：
🎈1. 思路一：本质是层序遍历二叉树，借助队列queue完成。先将根节点存入队列中，然后进入while循环，将队首元素出队并存入list数组中，然后将该队首节点右孩子入队，再将该队首节点左孩子入队。当队列为空时退出循环，list数组中即层序遍历结果。
🍤思路一：代码如下：
public class PrintFromTopToBottom_19 { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { if(root == null){ return new ArrayList<>(); } // 创建list数组 ArrayList<Integer> list = new ArrayList<>(); // 创建queue队列 Queue<TreeNode> queue = new LinkedList<>(); // 先将根节点入队 queue.offer(root); // 当队列不为空时 while (!queue.isEmpty()){ // 队首元素出队并存入list数组中 TreeNode node = queue.poll(); list.add(node.val); if(node.left != null){ // 将该队首节点右孩子入队 queue.offer(node.left); } if(node.right != null){ // 将该队首节点左孩子入队 queue.offer(node.right); } } return list; } }
🌳4. 二叉搜索树的后序遍历序列
描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
提示：
1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
4.参考下面的二叉搜索树，示例 1
编辑
解题思路：
🎈1. 思路一：首先我们应该知道，二叉搜索树性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
后序遍历：左右根方式遍历
所以我们判断依据如下：二叉搜索树BST的后序序列的合法序列是：对于一个序列S，最后一个元素是x （也就是root节点），如果去掉最后一个元素x的序列为 T，那么T满足：T可以分成两段，前一段（x的左子树）节点值都小于x，后一段（x的右子树）节点值大于x，且这两段（子树）都是合法的后序序列 ；当后一段（x的右子树）出现节点小于x时，说明不是合法的后序序列，return false 即可。
🍤思路一：代码如下：
public class VerifySquenceOfBST_20 { public boolean VerifySquenceOfBST(int [] sequence) { // 序列为空时，直接return false if(sequence == null || sequence.length == 0){ return false; } return VerifySquenceOfBSTHelper(sequence,0,sequence.length-1); } private boolean VerifySquenceOfBSTHelper(int[] sequence, int start, int end) { // 当子序列首索引大于等于尾索引，说明子序列都是合法后序序列，判断完毕，return true if(start >= end){ return true; } // 得到当前子序列首索引 int i = start; // 找到子序列中后一段（x的右子树）第一个大于root节点的位置 while(i < end && sequence[i] < sequence[end]){ i++; } // 遍历子序列中后一段（x的右子树）节点 for (int j = i; j < end; j++) { // 当后一段（x的右子树）出现节点小于x时，说明不是合法的后序序列，return false if(sequence[j] < sequence[end]){ return false; } } // 递归判断当前序列的前一段和后一段是否是合法的后序序列 return VerifySquenceOfBSTHelper(sequence,start,i-1) && VerifySquenceOfBSTHelper(sequence,i,end-1); } }
