1. 包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
分析
定义两个栈stack1,stack2,stack2的栈顶始终是当前栈中最小的值
push时stack1直接push,stack2需要判断栈顶元素是否大于push的值,大于的话直接push
pop时判断两个栈的栈顶元素是否一致,一致都pop,不一致stack1.pop
代码
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
if(stack2.isEmpty()){
stack2.push(node);
}else{
if(stack2.peek()>=node){
stack2.push(node);
}
}
}
public void pop() {
if(stack1.peek()==stack2.peek()){
stack1.pop();
stack2.pop();
}else{
stack1.pop();
}
}
public int top() {
return stack1.peek();
}
public int min() {
return stack2.peek();
}
}
2. 栈的压入弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
分析
原文链接
来源：牛客网
借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。
代码
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack1 = new Stack<Integer>();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack1.push(pushA[i]);
while(!stack1.isEmpty()&&stack1.peek()==popA[j]){
stack1.pop();
j++;
}
}
return stack1.isEmpty();
}
}
3. 从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
分析
- 用ArrayList集合存储从左到右的树节点,最后返回
- 用另一个ArrayList集合存储当前树节点,便于用remove方法移除下标为0的节点
- 先把根节点root加入到tree集合中,进入while循环,条件是tree.size!=0
- 在循环中用remove方法移除下标为0的节点,这个方法的返回值用temp保存
- 判断temp.left是否为null,不为null,我们可以把temp.left这个节点加到tree
- 接着判断temp.right是否为null,不为null把这个节点加到tree
- 最后我们把temp.val加入到list集合中,第一次循环就完成了对根节点的添加
代码
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<TreeNode> tree = new ArrayList<TreeNode>();
if(root==null){
return list;
}
tree.add(root);
while(tree.size()!=0){
TreeNode temp = tree.remove(0);
if(temp.left!=null){
tree.add(temp.left);
}
if(temp.right!=null){
tree.add(temp.right);
}
list.add(temp.val);
}
return list;
}
}
4. 二叉搜索树的后续遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
分析
二叉搜索树，举例如下：
原文连接
结合图中分析：
- 一棵 BST ：左孩子 < 根结点 < 右孩子
- 一棵 BST 的左子树或者右子树都是 BST
后序遍历是，左右根：[3, 4, 9, 5, 12, 11, 10]，结合图再从左往右分析后序序列，分析子树，可以发现：
- [3, 4, 9, 5] 10 [12, 11]
- [3, 4] 5 [9]
- [3] 4
- [12] 11
- [3, 4] 5 [9]
发现对于每一棵子树，它的根结点总是对应该子树的后序序列的最后一个数
那么，只需要不断地确定出左子树区间和右子树区间，并且判断：左子树区间的所有结点值 < 根结点值 < 右子树区间所有结点值，这个条件是否满足即可
编写一个isBST方法用来判断这个数组
代码
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length==0){
return false;
}
return isBST(sequence,0,sequence.length-1);
}
private boolean isBST(int[] seq,int start,int end){
if(start>=end){
return true;
}
int val = seq[end];
int split = start;
for(;split<end && seq[split]<val;split++);//找到根节点下的右孩子中最大的下标
for(int i = split;i<end;i++){
if(seq[i]<val){//右边的所有节点要比根节点大
return false;
}
}
return isBST(seq,start,split-1)&&isBST(seq,split,end-1);
}
}
二叉搜索树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
