《剑指offer》专题—算法训练 day04

ゝ一世哀愁。 2022-08-28 10:52 136阅读 0赞

### 文章目录 ###

*  《剑指offer》专题—算法训练day04
 *  一、反转链表
 *   *  思路一
     *  思路二
 *  二、合并有序链表
 *   *  思路一
     *  思路二
     *  递归思路
 *  三、树的子结构
 *   *  思路
 *  四、镜像二叉树
 *   *  思路
 *  未完待续...

# 《剑指offer》专题—算法训练day04 #

# 一、反转链表 #

[https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?][https_www.nowcoder.com_practice_75e878df47f24fdc9dc3e400ec6058ca]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]

## 思路一 ##

> 定义三个指针，进行迭代，整体右移，边移动，边翻转，保证不会断链

原链表

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]

第一次循环结束

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
第二次循环结束

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
第三次循环结束,跳出循环

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
最后两个节点进行翻转

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
原头节点的next 置为 null，更换新的头节点

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 6]

相关代码

> 无傀儡节点

/*
    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 new_head = null;// 新链表的头指针
            ListNode new_end = null; // 新链表的尾指针
            
            while(list1!=null && list2!=null){
        
                //1.找到我们要删除的节点
                ListNode p = list1.val<list2.val?list1:list2;
                
                // 2.在原链表中删除节点
                if(p == list1){
        
                    list1 = list1.next;
                }else{
        
                    list2 = list2.next;
                }
                
                //3.放入新链表中
                
                //3.1第一次插入节点|| 其他的情况
                if(new_head == null){
        
                    new_head = p;
                    new_end = p;
                }else{
        
                    //3.2 如果不是第一次插入，那么我们就将这个节点进行尾插
                    new_end.next = p;
                    new_end = p;
                }
            }
            
            // 如果两个链表的长度不一样，那么就会出现 
            // list1 == null || list2 == null
            
            if(list1 == null){
        
                new_end.next = list2;
            }
            
            if(list2 == null){
        
                new_end.next = list1;
            }
            
            return new_head;
        }
    }

## 递归思路 ##

> 重复的过程用递归来进行表示，缩小问题的规模

# 三、树的子结构 #

[https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?][https_www.nowcoder.com_practice_6e196c44c7004d15b1610b9afca8bd88]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 8]

## 思路 ##

> 二叉树都是递归定义的，所以递归操作是比较常见的做法  
> 首先明白：子结构怎么理解，可以理解成子结构是原树的子树(或者一部分)  
> 也就是说，B要是A的子结构，B的根节点+左子树+右子树，都在A中存在且构成树形结构

> 比较的过程要分为两步  
> 1.先确定起始位置  
> 2.在确定从该位置开始，后续的左右子树的内容是否一致

**相关代码**

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        
        
        public boolean isSameChild(TreeNode root1,TreeNode root2){
        
            // 这个函数用来判断左右子树是否相等
            if(root2 ==null){
        
    //             原子树全部遍历完，说明左右子树相等
                return true;
            }
            if(root1 == null){
        
    //             目标子树全部遍历完，说明左右子树不相等
                return false;
            }
            
            if(root1.val != root2.val){
        
                return false;
            }
            
            return isSameChild(root1.left,root2.left ) && isSameChild(root1.right,root2.right);
            
        }
        
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        
            
            if(root1 == null || root2== null){
        
                return false;
            }
            
            boolean result = false;
    //         1.先找对应的起始位置
            if(root1.val == root2.val){
        
                // 此时判断左右子树是否相等
                result = isSameChild(root1,root2);
            }
            
            // 如果resule 为 false ，那么没找到起始位置，继续从左子树找
            if(result != true){
        
                result = HasSubtree(root1.left,root2);
            }
            
            // 如果result 为 false ,那么没找到 起始位置，继续从右子树找
            if(result !=true){
        
                result = HasSubtree(root1.right,root2);
            }
            
            return result;
            
        }
    }

# 四、镜像二叉树 #

[https://www.nowcoder.com/questionTerminal/a9d0ecbacef9410ca97463e4a5c83be7][https_www.nowcoder.com_questionTerminal_a9d0ecbacef9410ca97463e4a5c83be7]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 9]

## 思路 ##

> 二叉树的常规操作是递归思路，缩小问题的规模  
> 这道题镜像二叉树，我们可以看到整颗树的左右子树都交换位置，我们缩小问题的规模，变成每颗子树的问题，每颗子树我们都需要进行交换左右子树的位置，进行递归操作.

**相关代码**

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.right;
            pRoot.right = pRoot.left;
            pRoot.left = temp;
            
            Mirror(pRoot.left);
            Mirror(pRoot.right);
            
            return pRoot;
            
        }
    }

好了，今天的内容就结束了，希望大家多多练习~~

**谢谢欣赏！！！**

**《剑指offer》 算法训练day5 敬请期待…**

# 未完待续… #

[https_www.nowcoder.com_practice_75e878df47f24fdc9dc3e400ec6058ca]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/653a2207db624f2ab04e44dcf5f0150e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/38138a6615d9450dbcda11c37a4a2237.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/21748f9428ee4961b68b4a05bd0332d2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/0f8fba8d1b1f474c8181b83e212baaff.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/c29e7eac13fd4b45b72be4cacf61c159.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/c4811d7024b64df1b8857e1f62f23e7b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/9d976852c3fb4aeb98493fe1b87af635.png
[https_www.nowcoder.com_practice_d8b6b4358f774294a89de2a6ac4d9337]: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/9d561b0947034616b964abc91459c035.png
[tmp]: /images/20220828/2300b99af8d94feb87fb3a4c34ddbcd2.png
[https_www.nowcoder.com_practice_6e196c44c7004d15b1610b9afca8bd88]: https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/8335b315dbb341b5a33d5ec8f4a5df51.png
[https_www.nowcoder.com_questionTerminal_a9d0ecbacef9410ca97463e4a5c83be7]: https://www.nowcoder.com/questionTerminal/a9d0ecbacef9410ca97463e4a5c83be7
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/34595b351a184311b0b2074cc0b4ed0b.png