✨对称二叉树有关的练习

• 前言
• ⛱️对称二叉树
• • 🥪🥪 递归
  • 🥪🥪迭代(使用队列)
• ⛱️相同的二叉树
• • 🥪🥪递归
  • 🥪🥪迭代法(使用队列)
• ⛱️判断t1树中是否有与t2树完全相同的子树
• • 🥪🥪题目描述
  • 🥪🥪思路
  • 🥪🥪代码
• ⛱️结束语

📃个人主页: 不断前进的皮卡丘
🌞博客描述: 梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记
🔥网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备----- 刷题神器

前言

学习算法，还有一些知识的时候，有时候看书后以为自己懂了，结果做题就发现自己没什么思路，为此，博主决定坚持刷题，这里给大家推荐一个适合大家做题复习，准备面试的网站点此进入，里面还有大量的面经，大家可以在面试之前去看看

我们可以看到里面根据不同知识层面分成对应的题库，算法也进行了对应的分类，十分的友好，接下来就开始今天的刷题之旅

⛱️对称二叉树

题目链接对称二叉树
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如： 下面这棵二叉树是对称的

下面这棵二叉树不对称。

🥪🥪 递归

1️⃣我们先看看根节点是否为空，根节点为空，则返回true，否则就得递归比较左右节点
2️⃣如果左右节点都为空，则返回true
3️⃣如果左节点为空，右节点不为空，或者左节点不为空，右节点为空，则返回false
4️⃣接下来，就是左右节点都非空的情况，我们就得比较节点的数值是否相等
5️⃣接下来就是递归遍历了，递归比较外侧(左节点的左孩子和右节点的右孩子比较)和内测(左节点的右孩子和右节点的左孩子)的情况

🥪🥪迭代(使用队列)

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

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        //先判断根节点
        if(pRoot==null) return true;
           Queue 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;
    }
        
        
    
}
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

⛱️相同的二叉树

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

两棵树上的节点数目都在范围 [0, 100] 内

🥪🥪递归

1️⃣我们先比较根节点
2️⃣如果两颗二叉树的根节点都为空，则返回true
3️⃣如果两棵树,其中一个根节点为空，另一个非空，则返回false
4️⃣如果两棵树根节点都非空，则比较数值，不相等返回false
5️⃣如果根节点数值相同，则递归比较左右子树
6️⃣左右子树等相同则返回true，否则返回false

🥪🥪迭代法(使用队列)

树与二叉树_习题

application/msword 0星 超过10%的资源 223KB

下载

1️⃣我们可以用两个队列来解决这个问题，队列保存树的结点
2️⃣逐层把二叉树的结点加入队列中
3️⃣判断逻辑和递归是一样的

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

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

🥪🥪题目描述

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

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

数据范围：树的节点数满足 0 < n \le 5000000 进阶：空间复杂度: O(1)O(1)，时间复杂度 O(n)O(n)

🥪🥪思路

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

🥪🥪代码

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);
    }
}
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
37
38
39
40
41

⛱️结束语

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