17. 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路： 首先判断两棵树是否相等，我们可以利用递归来判断。即如果根节点相等，判断左右孩子是否相等。对于这个题目，我们可以转化为3种情况，首先判断root1和root2自身是否相等，不相等，则就剩下两种情况，即root1的左子树和root1的右子树和root2是否相同；仍不相同则递归向下，有一个相同，则返回true。
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
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean isSubtree(TreeNode root1, TreeNode root2){
if(root2 == null) return true;
if(root1 == null) return false;
if(root2.val != root1.val) return false;
else return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
}
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null) return false;
else return isSubtree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
}
18. 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5
思路： 递归交换左右子树。
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
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode tmp = new TreeNode(0);
public void Mirror(TreeNode root) {
if(root != null){
tmp = root.right;
root.right = root.left;
root.left = tmp;
Mirror(root.left);
Mirror(root.right);
}
}
}
19. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 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.
思路： 代码比较蠢，看着一点都不优雅，拍脑袋写的，有空再优化一下。思路非常简单，对着矩阵一圈圈打印即可，使用count计数，当count等于矩阵内数字总数的时候返回即可。
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
32
33
34
35
36
37
38
39
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
int n = matrix.length; int m = matrix[0].length;
int total = m * n; int count = 0; int offset = 0;
ArrayList<Integer> output = new ArrayList<Integer>();
while(true){
for(int j = offset; j < m - offset; j++){
output.add(matrix[offset][j]);
count++;
if(count == total){
return output;
}
}
for(int i = 1 + offset; i < n - offset; i++){
output.add(matrix[i][m - 1 - offset]);
count++;
if(count == total){
return output;
}
}
for(int j = m - 2 - offset; j >= offset; j--){
output.add(matrix[n - 1 - offset][j]);
count++;
if(count == total){
return output;
}
}
for(int i = n - 2 - offset; i >= 1 + offset; i--){
output.add(matrix[i][offset]);
count++;
if(count == total){
return output;
}
}
offset ++;
}
}
}