[算法刷题笔记]二叉树练习(2):对称二叉树有关的练习

我就是我 2024-04-21 08:01 161阅读 0赞

> #### ✨对称二叉树有关的练习 ####
> 
>  *  前言
>  *  ⛱️对称二叉树
>  *   *  ?? 递归
>      *  ??迭代(使用队列)
>  *  ⛱️相同的二叉树
>  *   *  ??递归
>      *  ??迭代法(使用队列)
>  *  ⛱️判断t1树中是否有与t2树完全相同的子树
>  *   *  ??题目描述
>      *  ??思路
>      *  ??代码
>  *  ⛱️结束语
> 
>   
> ?个人主页: [不断前进的皮卡丘][Link 1]  
> ?博客描述: **梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记**  
> **?网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备**\----- [刷题神器][Link 2]

## 前言 ##

> 学习算法，还有一些知识的时候，有时候看书后以为自己懂了，结果做题就发现自己没什么思路，为此，博主决定坚持刷题，这里给大家推荐一个适合大家做题复习，准备面试的网站[点此进入][Link 2]，里面还有大量的面经，大家可以在面试之前去看看  
> ![在这里插入图片描述][15ff82da90f44be2a95cb48c93105248.png]  
> 我们可以看到里面根据不同知识层面分成对应的题库，算法也进行了对应的分类，十分的友好，接下来就开始今天的刷题之旅

## ⛱️对称二叉树 ##

题目链接[对称二叉树][Link 3]  
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）  
例如： 下面这棵二叉树是对称的  
![在这里插入图片描述][ec3536e2d9c244539c77cae2927cbf39.png]  
下面这棵二叉树不对称。  
![在这里插入图片描述][12e11936fef84ef3bcf3181d0a07024f.png]

### ?? 递归 ###

> ![在这里插入图片描述][3ee3050546f947e3b88077e85dcb7535.png]  
> 1️⃣我们先看看根节点是否为空，根节点为空，则返回true，否则就得递归比较左右节点  
> 2️⃣如果左右节点都为空，则返回true  
> 3️⃣如果左节点为空，右节点不为空，或者左节点不为空，右节点为空，则返回false  
> 4️⃣接下来，就是左右节点都非空的情况，我们就得比较节点的数值是否相等  
> 5️⃣接下来就是递归遍历了，递归比较外侧(左节点的左孩子和右节点的右孩子比较)和内测(左节点的右孩子和右节点的左孩子)的情况  
> ![在这里插入图片描述][15fb515066f3498aaffa05fb43ae8c81.png]

### ??迭代(使用队列) ###

思路和刚刚递归是一样的，只是实现方法不一样  
具体的图解大家可以去里面看看[题解][Link 3]

public class Solution {
        
        boolean isSymmetrical(TreeNode pRoot) {
        
            //先判断根节点
            if(pRoot==null) return true;
               Queue<TreeNode> deque = new LinkedList<>();
            deque.offer(pRoot.left);
            deque.offer(pRoot.right);
            while (!deque.isEmpty()) {
        
                TreeNode leftNode = deque.poll();
                TreeNode rightNode = deque.poll();
                if (leftNode == null && rightNode == null) {
        
                    continue;
                }
                 if (leftNode == null && rightNode != null) {
        
                    return false;
                }
                 if (leftNode != null && rightNode == null) {
        
                    return false;
               }
                if (leftNode.val != rightNode.val) {
        
                     return false;
                }
              
                // 这里顺序与使用Deque不同
                deque.offer(leftNode.left);
                deque.offer(rightNode.right);
                deque.offer(leftNode.right);
                deque.offer(rightNode.left);
            }
            return true;
        }
            
            
        
    }

## ⛱️相同的二叉树 ##

[相同的二叉树][Link 4]  
给定两个根结点分别为 root1root1 和 root2root2 二叉树，请判断这两棵树是否完全相同。  
数据范围:  
−104≤Node.val≤104−10  
4  
≤Node.val≤10  
4

两棵树上的节点数目都在范围 \[0, 100\] 内  
![在这里插入图片描述][5021f2d5344847eab9ef7bb8d726bc86.png]  
![在这里插入图片描述][babb222578fe4f5b827aaa5e8c199fe3.png]  
![在这里插入图片描述][7c392f97adbc4f2ca84ddc8be0c3cd5a.png]

### ??递归 ###

> 1️⃣我们先比较根节点  
> 2️⃣如果两颗二叉树的根节点都为空，则返回true  
> 3️⃣如果两棵树,其中一个根节点为空，另一个非空，则返回false  
> 4️⃣如果两棵树根节点都非空，则比较数值，不相等返回false  
> 5️⃣如果根节点数值相同，则递归比较左右子树  
> 6️⃣左右子树等相同则返回true，否则返回false  
> ![在这里插入图片描述][22f7552bbb6640ea9ff80f646726a0cb.png]  
> ![在这里插入图片描述][8a9b76adaccc4576b3146892c9b9b68d.png]

### ??迭代法(使用队列) ###

> 1️⃣我们可以用两个队列来解决这个问题，队列保存树的结点  
> 2️⃣逐层把二叉树的结点加入队列中  
> 3️⃣判断逻辑和递归是一样的  
> ![在这里插入图片描述][5f3d7f70161c44ae8a71317c35a153b8.png]

## ⛱️判断t1树中是否有与t2树完全相同的子树 ##

[判断t1树中是否有和t2树完全相同的子树][t1_t2]

### ??题目描述 ###

给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。

子树指一棵树的某个节点的全部后继节点

数据范围：树的节点数满足 0 < n \\le 5000000<n≤500000，树上每个节点的值一定在32位整型范围内  
进阶：空间复杂度: O(1)O(1)，时间复杂度 O(n)O(n)

![在这里插入图片描述][09a5bd84cc34464db1242f0db1268dbd.png]

### ??思路 ###

> 其实这道题目和判断两棵树是否相同是差不多思路的，两棵树A,B，B如果满足是A的子树，那么就会有三种情况  
> 1️⃣两棵树相同  
> 2️⃣B是A的左子树(B和A的左子树相同)  
> 3️⃣B是A的右子树(B和A的右子树相同)  
> 我们可以看出解决这个大问题，其实有可以划分成若干个相同的小问题，可以使用递归来解决  
> ![在这里插入图片描述][76eef00d2f9a49e8859de2626d17c3f5.png]

### ??代码 ###

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param root1 TreeNode类 
         * @param root2 TreeNode类 
         * @return bool布尔型
         */
        public boolean isContains (TreeNode root1, TreeNode root2) {
        
            // write code here
              if (root1==null||root2==null){
        
                return false;
            }
            return sameRootDfs(root1,root2)||isContains(root1.left,root2)||isContains(root1.right,root2);
    
        }
           private boolean sameRootDfs(TreeNode A, TreeNode B){
        
            //这里如果B为空并且A为空，表示A和B已经遍历完成，并且经过了A.val!=B.val的考验
            if(A==null&&B==null){
        
                return true;
            }
    
            //1.A为空表示B不为空，表示两者不同
            //2.B为空原理和1一样
            //3.A和B的值不一样，表示两者不同
            if (A==null||B==null||A.val!=B.val){
        
                return false;
            }
            //当前节点比较完之后还要继续判断左右子节点
            return sameRootDfs(A.left,B.left)&&sameRootDfs(A.right,B.right);
        }
    }

![在这里插入图片描述][902baff038da4157ac8652eeac4ad934.png]

## ⛱️结束语 ##

> 希望大家可以自己动手练习一下，算法光看是不行的，必须亲自动手敲代码，有时候你会发现自己有思路，但是又写不出来，这就是缺乏练习的原因。大家平时在做题的时候，可以多思考，多总结。  
> 刚开始的时候，我们可能遇到一种新的题型，完全没有思路的时候，其实可以先去看看别人的思路，还有题解，把它理解下来，然后把代码敲出来(不要复制粘贴,我们根据自己的理解敲出代码这样才有效果，如果中途卡住了，也可以再回过头去看看)  
> 另外，为了检测一下我们是否真正的掌握，我们可以去做几道相似的题目巩固一下，顺便检验一下自己的成果。  
> [点此跳转去练习][Link 2]![在这里插入图片描述][5e96aa56fa7445e49d327faa99883c79.png]  
> 这里面有对应的题目，比如链表，二叉树等等，我们可以找到自己想要练习的题目，根据标签就可以进行筛选了，非常的方便。  
> 算法不是看会的，而是在做题中学会的，这是我的个人看法，刚开始由浅入深，不要太追求效率，先把自己的思路写出来，然后逐渐培养思维，然后在有一定的积累以后，我们再来追求效率，再来追求一题多解。算法贵在坚持，不可能一朝一夕就成为大牛。  
> 如果有的小伙伴急着找工作的话，如果时间比较紧张，那么，我们可以先把一些面试高频的题目给做了，像这里面就列举出来了面试必刷题目。  
> [一起坚持下去，冲冲冲][Link 2]![在这里插入图片描述][c25b6a6f7b15469da28ef58e5b87d303.png]

[Link 1]: https://blog.csdn.net/qq_52797170?spm=1010.2135.3001.5343
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_pkq_sf
[15ff82da90f44be2a95cb48c93105248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/22b3357734f341bb82fe660d33fd0215.png
[Link 3]: https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=196&tqId=37058&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E5%25AF%25B9%25E7%25A7%25B0&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%E5%AF%B9%E7%A7%B0
[ec3536e2d9c244539c77cae2927cbf39.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/479bc0352e6f4665b6020b483eaafae8.png
[12e11936fef84ef3bcf3181d0a07024f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/c3d44703f1574ad0b7d60497a1e72c22.png
[3ee3050546f947e3b88077e85dcb7535.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/67b4becee2154f24a57ec1b6da1dcec4.png
[15fb515066f3498aaffa05fb43ae8c81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/d324e3c030894a628a5940a9c80d87e8.png
[Link 4]: https://www.nowcoder.com/practice/5a3b2cf4211249c89d6ced7987aeb775?tpId=196&tqId=40271&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E7%259B%25B8%25E5%2590%258C&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%E7%9B%B8%E5%90%8C
[5021f2d5344847eab9ef7bb8d726bc86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/b97fff1c03554a14b635e22d5f1c90ff.png
[babb222578fe4f5b827aaa5e8c199fe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/3fdf0943b2bb43798a44a8e2b7e31ae0.png
[7c392f97adbc4f2ca84ddc8be0c3cd5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/8d7e2916827e4901a13bc91de06ace71.png
[22f7552bbb6640ea9ff80f646726a0cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/4cdd0e1f7abc4589990ec6384eafb6ad.png
[8a9b76adaccc4576b3146892c9b9b68d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/f3615ac3e6a74924bd0dd5f045c23ad7.png
[5f3d7f70161c44ae8a71317c35a153b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/80d40657c2404a1da5199f61fc7b5bfc.png
[t1_t2]: https://www.nowcoder.com/practice/4eaccec5ee8f4fe8a4309463b807a542?tpId=196&tqId=37155&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%2520&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%20
[09a5bd84cc34464db1242f0db1268dbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/03bd72388f8b48e98b09e9dca2bf3af7.png
[76eef00d2f9a49e8859de2626d17c3f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/a6f9526513d642a495c4f8b184c35403.png
[902baff038da4157ac8652eeac4ad934.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/39f7d436b8e94a3da4a4868baeac77f3.png
[5e96aa56fa7445e49d327faa99883c79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/2a72f2610f0f4baa88ea53ebed190e30.png
[c25b6a6f7b15469da28ef58e5b87d303.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/7cfedf64f40c46f2b728ccdc4589e5de.png