18.二叉树的镜像
操作给定的二叉树,将其变换为源二叉树的镜像。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root != null){
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left!=null) Mirror(root.left);
if(root.right!=null) Mirror(root.right);
}
}
}
19.顺时针打印矩阵(这道题有难度)
见书P161
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
知识点:
关于值传递和引用传递可以得出这样的结论:
- 基本数据类型传值,对形参的修改不会影响实参;
- 引用类型传引用,形参和实参指向同一个内存地址(同一个对象),所以对参数的修改会影响到实际的对象;
- String, Integer, Double等immutable的类型特殊处理,可以理解为传值,最后的操作不会修改实参对象。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
if(matrix == null) return null;
ArrayList<Integer> result = new ArrayList<>();
int start = 0;
while(start*2<matrix.length&&start*2<matrix[0].length){
printMatrixCircle(matrix,start,result);
start++;
}
return result;
}
public void printMatrixCircle(int [][] matrix,int start,ArrayList<Integer> result){
int endX = matrix[0].length - 1 - start;
int endY = matrix.length - 1 - start;
for(int i = start;i <= endX;i++){
result.add(matrix[start][i]);
}
if(start < endY){
for(int i = start +1;i <= endY;i++)
result.add(matrix[i][endX]);
}
if(start<endX&&start<endY)
for(int i = endX -1;i>=start;i--)
result.add(matrix[endY][i]);
if(start<endX&&start<endY-1)
for(int i = endY -1;i>start;i--)
result.add(matrix[i][start]);
}
}
20 包含min函数的栈
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
import java.util.Stack;
public class Solution {
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
int min;
public void push(int node) {
stack.push(node);
if(minStack.empty())
min = node;
else
min = Math.min(minStack.peek(),node);
minStack.push(min);
}
public int pop() {
minStack.pop();
return stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}