本文已收录于专栏 🌻 《刷题笔记》

文章目录

• 前言
• 🎨 1、合并两个有序链表
• • 题目描述
  • 思路一（递归）
  • 思路二（双指针）
• 🎨 2、树的子结构
• • 题目描述
  • 思路一（递归）
• 🎨 3、二叉树的镜像
• • 题目描述
  • 思路一（递归）
• 🎨 4、顺时针打印矩阵
• • 题目描述
  • 思路一（边界模拟法）

前言

题目来源参考阿秀学长的刷题笔记，小戴只是把 C++的题解改成了 Java版本，并整理了其他思路，便于自己的学习~

如果解题有更好的方法，本文也会及时进行更新~

希望对你有帮助~ 一起加油哇~

🎨 1、合并两个有序链表

牛客原题链接

题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的

思路一（递归）

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val < list2.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
        
    }
}

思路二（双指针）

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        // 创建一个头结点
        ListNode head = new ListNode(0);
        ListNode cur = head;

        while(list1!=null && list2!=null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        if(list1 != null){
            cur.next = list1;
        }else{
            cur.next = list2;
        }

        return head.next;
    }
}

🎨 2、树的子结构

牛客原题链接

题目描述

输入两棵二叉树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) {

        if (root1 == null || root2 == null) {
            return false;
        }

        return HasSub(root1, root2) || HasSubtree(root1.left, root2) ||
               HasSubtree(root1.right, root2);
    }

    public boolean HasSub(TreeNode root1, TreeNode root2) {
        // 不匹配的情况有很多，先找匹配的情况
        // 遍历完root2，root2为空时，说明root2的所有结点都与root1的子结构匹配上
        if (root2 == null) {
            return true;
        }

        // 不匹配的情况
        // root2不为null的时候，root1为null了，显然不匹配
        if(root1 == null){
            return false;
        } 
        // root1和root2都不为空，但是数值不同，所以不匹配
        if(root1.val != root2.val){
            return false;
        }

        // 到这里说明这个点是匹配的，继续判断左子树和右子树是否匹配
        return HasSub(root1.left,root2.left) && HasSub(root1.right,root2.right);
    }
}

🎨 3、二叉树的镜像

牛客原题链接

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像

思路一（递归）

先把根节点的左右子树进行交换，再递归子树进行镜像，不断交换底下的左右节点

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        // 空树返回
        if(pRoot == null) return null;
        // 交换
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;
        // 递归
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

🎨 4、顺时针打印矩阵

牛客原题链接

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：

[[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 {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer> res = new ArrayList<>();
       if(matrix.length == 0){
        return res;
       }
       // 左边界
       int left = 0;
       // 右边界
       int right = matrix[0].length - 1;
       // 上边界
       int up = 0;
       // 下边界
       int down = matrix.length - 1;
       while(left <= right && up <= down){
            // 上边界的从左到右
            for(int i = left; i <=right; i++){
                res.add(matrix[up][i]);
            }
            up++;
            if(up > down){
                break;
            }
            // 右边界的从上到下
            for(int i = up; i <= down; i++){
                res.add(matrix[i][right]);
            }
            right--;
            if(left > right){
                break;
            }
            // 下边界的从右到左
            for(int i = right; i >= left; i--){
                res.add(matrix[down][i]);
            }
            down--;
            if(up > down){
                break;
            }
            // 左边界的从下到上
            for(int i = down; i >= up; i--){
                res.add(matrix[i][left]);
            }
            left++;
            if(left > right){
                break;
            }
       }
       return res;
    }
}