【lc刷题 day2】树的子结构 二叉树的镜像 对称的二叉树 顺时针打印矩阵

剑指offer 26 树的子结构 medium

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;
        return isSub(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    boolean isSub(TreeNode A, TreeNode B){
        if(B==null) return true;
        if(A==null) return false;
        if(A.val==B.val) return isSub(A.left,B.left)&&isSub(A.right,B.right);
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

md好难，没做出来，估计下次做还是做不出来，主要使用dfs
先把这题放在这里吧，等学会dfs再来看看
下面这个是我一开始写的，测试用例无法通过，想不太明白
时间复杂度O(MN) 空间复杂度O(M）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B==null) return false;
        return isSub(A,B)||isSub(A.left,B)||isSub(A.right,B);
    }
    boolean isSub(TreeNode A, TreeNode B){
        if(B==null) return true;
        if(A.val==B.val) return isSub(A.left,B.left)&&isSub(A.right,B.right);
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

剑指Offer 27.二叉树的镜像 easy

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        mirror(root);
        return root;
    }
    void mirror(TreeNode node){
        if(node==null) return;
        TreeNode n=node.left;
        node.left=node.right;
        node.right=n;
        mirror(node.left);
        mirror(node.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

秒了，使用递归
时间复杂度O(n),空间复杂度O(n)

剑指Offer 28.对称的二叉树 easy

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return mirror(root.left,root.right);
    }
    boolean mirror(TreeNode A,TreeNode B){
        if(A==null&&B==null) return true;
        if(A==null||B==null) return false;
        return A.val==B.val&&mirror(A.left,B.right)&&mirror(A.right,B.left);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

一开始的思路是用上一题镜像把二叉树反转，然后再比较两个树是否相等，但是这样需要更多的空间
递归判断A的左子树和B的右子树，A的右子树和B的左子树是否相等即可
时间复杂度O(n),空间复杂度O(n)

剑指Offer 29.顺时针打印矩阵 easy

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0) return new int[0];
        int top=0,bottom=matrix.length-1,left=0,right=matrix[0].length-1;
        int len=(bottom+1)*(right+1);
        int[] res=new int[len];
        int p=0;
        while(p<len){
            for(int i=left;i<=right;i++){
                res[p]=matrix[top][i];
                p++;
            }
            top++;
            if(p>=len) break;
            for(int i=top;i<=bottom;i++){
                res[p]=matrix[i][right];
                p++;
            }
            right--;
            if(p>=len) break;
            for(int i=right;i>=left;i--){
                res[p]=matrix[bottom][i];
                p++;
            }
            bottom--;
            if(p>=len) break;
            for(int i=bottom;i>=top;i--){
                res[p]=matrix[i][left];
                p++;
            }
            left++;
            if(p>=len) break;
        }
        return res;
    }
}
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

这道题有两个地方需要注意

1. 边界条件考虑充分
2. 在循环的过程中随时判断是否p>=len
   时间复杂度O(mn) 空间复杂度O(1)

每次拖延症都搞到好晚，哭了