未经本人允许，不得转载
今天心情真好，那么正式开始：
第十七题：树的子结构
难易度：⭐⭐
题目描述:
现在给定 TreeNode类
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
输入两棵树A,B;
判断B是不是A的子结构(我们约定空树不是任意一棵树的子结构)
例如：
A:
8
/ \
8 7
/ \
9 2
/ \
4 7
B:
8
/ \
9 2
则：B为A的子结构
本题的思路为：
首先遍历A树，如果遍历到的节点的val值等于B树的根节点的val，那么再去判断以这个节点为根的树是否"包含" B树。本题的重点是对二叉树遍历的考察以及对递归过程的理解。代码中还是有很多细节需要去研究的，比如：当发现A树的某个节点的值等于B树的根节点的值后，如何判断B树包含在A树中？各种case的判定还是比较难想的。
代码如下：
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
boolean res = false;
if(root1.val == root2.val){
// 判断A树中是否包含B树
res = doesTree1HaveTree2(root1,root2);
}
if(!res){
res = HasSubtree(root1.left,root2);
}
if(!res){
res = HasSubtree(root1.right,root2);
}
return res;
}
public boolean doesTree1HaveTree2(TreeNode node1,TreeNode node2){
if(node2 == null){
return true;
}
if(node1 == null){
return false;
}
if(node1.val != node2.val){
return false;
}
return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
}
}
第十八题：二叉树的镜像
难易度：⭐
题目描述：
给定TreeNode 类
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
操作给定的二叉树，将其变为源二叉树的镜像
例如：
源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
本题思路分析：
二叉树和递归是紧密相连的，因为二叉树的遍历就是递归。不难发现，对二叉树取镜像，实际上就是将每个节点的左子树和右子树交换位置，我们只需要对二叉树先序遍历，然后交换遍历到的节点的左子树和右子树的位置即可。
代码如下：
public class Solution {
public void Mirror(TreeNode root) {
if(root != null){
mirrorProcess(root);
Mirror(root.left);
Mirror(root.right);
}
}
public static void mirrorProcess(TreeNode node){
TreeNode helpNode = node.left;
node.left = node.right;
node.right = helpNode;
}
}
如果对二叉树的遍历不熟悉，需要好好熟悉。面试官有可能继而希望你可以写出非递归的版本：
import java.util.Stack;
public class Solution {
public void Mirror(TreeNode root) {
if(root != null){
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
mirrorProcess(root);
if(root.right != null){
stack.push(root.right);
}
if(root.left != null){
stack.push(root.left);
}
}
}
}
public static void mirrorProcess(TreeNode node){
TreeNode helpNode = node.left;
node.left = node.right;
node.right = helpNode;
}
}
对于二叉树的先序遍历，中序遍历，后序遍历的非递归实现需要能达到白板coding秒写的程度。
第十九题：顺时针打印矩阵
难易度：⭐⭐
题目描述:
转圈打印矩阵
给定一个整型矩阵matrix，请按照顺时针转圈的方式打印它
例如：
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
要求：
额外空间复杂度为O(1)
解题思路：
将顺时针转圈打印转换成一圈一圈地打印，只要知道矩阵左上角的点和矩阵右下角的点就可以将打印出一圈。打印的顺序如图：
接下来，左上角的点和右下角的点横纵坐标减一，再继续打印内圈的部分，这样就和顺时针转圈打印的效果是一样的。重点是需要考虑好几种情况：
1.当矩阵压缩到只剩一个数字时
2.当矩阵压缩到横形的棒状时
3.当矩阵压缩到竖形的棒状时
本题在我的文章 《栈，队列，矩阵相关基础题目及答案》中，已经介绍过一遍了。本题要返回一个ArrayList结果，代码略有不同，但思路一模一样，代码如下：
import java.util.ArrayList;
public class Solution {
private ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> printMatrix(int [][] matrix) {
int startRow = 0;
int startColumn = 0;
int endRow = matrix.length - 1;
int endColumn = matrix[0].length - 1;
while(startRow <= endRow && startColumn <= endColumn){
printProcess(matrix,startRow,startColumn,endRow,endColumn);
startRow++;
endRow--;
startColumn++;
endColumn--;
}
return arrayList;
}
public void printProcess(int[][] matrix,int startRow,int startColumn,int endRow,int endColumn){
if(startRow == endRow && startColumn == endColumn){
arrayList.add(matrix[startRow][startColumn]);
}
if(startRow == endRow && startColumn < endColumn){
for(int i = startColumn;i <= endColumn;i++){
arrayList.add(matrix[startRow][i]);
}
}
if(startRow < endRow && startColumn == endColumn){
for(int i = startRow;i <= endRow;i++){
arrayList.add(matrix[i][startColumn]);
}
}
if(startRow < endRow && startColumn < endColumn){
for(int i = startColumn;i < endColumn;i++){
arrayList.add(matrix[startRow][i]);
}
for(int i = startRow;i < endRow;i++){
arrayList.add(matrix[i][endColumn]);
}
for(int i = endColumn;i > startColumn;i--){
arrayList.add(matrix[endRow][i]);
}
for(int i = endRow;i > startRow;i--){
arrayList.add(matrix[i][startColumn]);
}
}
}
}
代码虽然看上去多，但是捋顺思路后，实际上很简单。
京公网安备 11010502036488号