20. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
思路： 用一个栈用来存储元素，用另一个列表或栈存储最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
Stack<Integer> data = new Stack<Integer>();
ArrayList<Integer> minData = new ArrayList<Integer>();
public void push(int node){
data.push(node);
if(minData.size() == 0) minData.add(node);
else if(node < minData.get(minData.size() - 1)){
minData.add(node);
}
}
public void pop(){
int num = data.pop();
if(num == minData.get(minData.size() - 1)) minData.remove(minData.size() - 1);
}
public int top(){
if(!data.empty()){
return data.peek();
}
return 0;
}
public int min(){
return minData.get(minData.size()-1);
}
}
21. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路： 将入栈序列挨个压入栈，每压入一个元素，判断栈顶元素与出栈序列第一个元素是否相等，若相等，则弹出栈顶，并将出栈序列的下标后移继续与栈顶匹配。直到某个栈顶元素与出栈序列当前元素不等，继续将入栈序列压入栈，若最后该栈不为空，则出栈序列与入栈序列不配；为空，则匹配。
例，入栈序列1，2，3，4，5；出栈序列4，3，5，1，2
1入栈，1!=4
2入栈，2!=4
3入栈，3!=4
4入栈，4==4，弹出4；3==3，弹出3；2！=5
5入栈，5==5，弹出5；2!=1
循环结束，此时栈内还有1，2，不为空，则不匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> sta = new Stack<Integer>();
for(int i = 0, j = 0;i < pushA.length; i++){
sta.push(pushA[i]);
while((j < popA.length) && (popA[j] == sta.peek())){
sta.pop();
j++;
}
}
return sta.empty();
}
}
22. 从上往下逐层打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路： 将节点存入队列，当它出队时，将其节点值存到output中，并将该节点的左右孩子逐个存入队列。
例，一颗二叉树，节点足层打印顺序为，1，2，3，4，5，6，7。
将1存入队列，此时队列只有1节点。进入循环：
此时队列头部为1，1出队，output中存取节点1的值，将1的左右孩子2，3入队；
此时队列头部为2，2出队，output中存取节点2的值，将2的左右孩子4，5入队；
此时队列头部为3，3出队，output中存取节点3的值，将3的左右孩子6，7入队；
此时队列头部为4，4出队，output中存取节点4的值，没有孩子节点；
此时队列头部为5，5出队，output中存取节点5的值，没有孩子节点；
……
当队列为空，跳出循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> output = new ArrayList<Integer>();
ArrayList<TreeNode> node = new ArrayList<TreeNode>();
if(root!=null){
node.add(root);
while(!node.isEmpty()){
TreeNode tmp = node.remove(0);
output.add(tmp.val);
if(tmp.left!=null) node.add(tmp.left);
if(tmp.right!=null) node.add(tmp.right);
}
}
return output;
}
}