题目1
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
if(root1!=null&&root2!=null){
if(root1.val==root2.val){
result=checkSubTree(root1,root2);
}
if(!result)
result = HasSubtree(root1.left,root2);
if(!result)
result = HasSubtree(root1.right,root2);
}
return result;
}
public boolean checkSubTree(TreeNode root1,TreeNode root2) {
if(root2==null)
return true;
if(root1==null)
return false;
if(root1.val!=root2.val)
return false;
return checkSubTree(root1.left,root2.left)&&checkSubTree(root1.right,root2.right);
}
}题目描述（二叉树的反转）
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/
6 10
/ /
5 7 9 11
镜像二叉树
8
/
10 6
/ /
11 9 7 5
/**
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)
return;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
Mirror(root.left);
Mirror(root.right);
}
}题目3
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 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.
这个做了有点久，第一次做的如下（分四种主要情况）：
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<Integer> printMatrix(int [][] matrix) {
if(matrix==null)
return list;
int a=0,b=0,a_length = matrix.length,b_length = matrix[0].length;
while(a_length>=1&&b_length>=1){
sysoutArray(matrix,a,b,a_length,b_length);
a++;
b++;
a_length-=2;
b_length-=2;
}
return list;
}
public void sysoutArray(int [][] matrix,int a,int b,int a_length,int b_length){
//单个的情况
if(a_length==b_length&&a_length==1){
list.add(matrix[a][b]);
return;
}
//两种单行的情况
if(a_length==1){
for(int i=b;i<b+b_length;i++)
list.add(matrix[a][i]);
return;
}
if(b_length==1){
for(int i=0;i<a+a_length;i++)
list.add(matrix[i][b]);
return;
}
//可以顺时针旋转打印的情况
for(int i=b;i<b+b_length-1;i++)
list.add(matrix[a][i]);
for(int i=a;i<a+a_length-1;i++)
list.add(matrix[i][b+b_length-1]);
for(int i=b+b_length-1;i>=a+1;i--)
list.add(matrix[a+a_length-1][i]);
for(int i=a+a_length-1;i>=a+1;i--)
list.add(matrix[i][b]);
}
}题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
import java.util.Stack;
public class Solution {
private Stack<Integer> stack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>();
private Integer minFlag=null;
public void push(int node) {
if(minFlag!=null){
int min = minStack.peek();
if(node<min){
minFlag=node;
minStack.push(node);
}else{
minFlag=min;
minStack.push(min);
}
}else{
minFlag=node;
minStack.push(node);
}
stack.push(node);
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA==null||popA==null||pushA.length==0||popA.length==0)
return false;
Stack<Integer> stack = new Stack<Integer>();
int index=0;
for(int i=0;i<pushA.length;i++){
stack.push(pushA[i]);
while(!stack.empty()&&stack.peek()==popA[index]){
stack.pop();
index++;
}
}
return stack.empty();
}
}题目6
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。(二叉树的层序遍历)
import java.util.*;
/**
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>();
if(root==null)
return list;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode treeNode = queue.poll();
if(treeNode.left!=null){
queue.offer(treeNode.left);
}
if(treeNode.right!=null){
queue.offer(treeNode.right);
}
list.add(treeNode.val);
}
return list;
}
}