[java刷算法]牛客—剑指offer树的子结构，对称树，树的镜像

• 🧛‍♂️个人主页：杯咖啡
• 💡进步是今天的活动，明天的保证！
• ✨目前正在学习：SSM框架,算法刷题
• 👉本文收录专栏 ： java刷算法牛客—剑指offer
• 🙌牛客网，刷算法过面试的神级网站，用牛客你也牛。 👉免费注册和我一起学习刷题👈
• 🐳希望大家多多支持🥰一起进步呀！
• 😎The man who fears losing has already lost.
  怕输的人已经输了。 - 《权力的游戏》

---

✨今日三剑

JZ26 树的子结构
JZ27 二叉树的镜像
JZ28 对称的二叉树

---

---

JZ26 树的子结构

题目描述

思路详解

本题我们使用两层前序遍历
既然是要找到A树中是否有B树这样子树，如果是有子树肯定是要遍历这个子树和B树，将两个的节点一一比较，但是这样的子树不一定就是A树根节点开始的，所以我们还要先找到子树可能出现的位置。
既然是可能的位置，那我们可以对A树的每个节点前序递归遍历，寻找是否有这样的子树，而寻找是否有子树的时候，我们就将A树与B树同步前序遍历，依次比较节点值。

代码与结果

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 {
    private boolean recursion(TreeNode root1, TreeNode root2){
        //当一个节点存在另一个不存在时
        if(root1 == null && root2 != null)  
            return false;
        //两个都为空则返回
        if(root1 == null || root2 == null)  
            return true;
        //比较节点值
        if(root1.val != root2.val)
            return false;
        //递归比较子树
        return recursion(root1.left, root2.left) && recursion(root1.right, root2.right);
    }

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //空树
        if(root2 == null) 
            return false;
        //一个为空，另一个不为空
        if(root1 == null && root2 != null)
            return false;
        if(root1 == null || root2 == null)
            return true;
        //递归比较
        boolean flag1 = recursion(root1, root2);  
        //递归树1的每个节点
        boolean flag2 = HasSubtree(root1.left, root2);  
        boolean flag3 = HasSubtree(root1.right, root2);
        return flag1 || flag2 || flag3;
    }

}
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
42
43
44
45
46
47

JZ27 二叉树的镜像

题目描述

思路详解

因为我们需要将二叉树镜像，意味着每个左右子树都会交换位置，如果我们从上到下对遍历到的节点交换位置，但是它们后面的节点无法跟着他们一起被交换，因此我们可以考虑自底向上对每两个相对位置的节点交换位置，这样往上各个子树也会被交换位置。
自底向上的遍历方式，我们可以采用后序递归的方法。

代码与结果

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) {
        //空树返回
        if(pRoot == null)
            return null;
        //先递归子树
        TreeNode left = Mirror(pRoot.left); 
        TreeNode right = Mirror(pRoot.right);
        //交换
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }
}
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

JZ28 对称的二叉树

题目描述

思路详解

前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。
不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序递归可以使用递归：
终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
返回值： 每一级将子问题是否匹配的结果往上传递。
本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。

代码与结果

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 {
   boolean recursion(TreeNode root1, TreeNode root2){
        //可以两个都为空
        if(root1 == null && root2 == null)
            return true;
        //只有一个为空或者节点值不同，必定不对称
        if(root1 == null || root2 == null || root1.val != root2.val)
            return false;
        //每层对应的节点进入递归比较
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }
    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    }
}
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

---

$原创不易，还希望各位大佬支持一下$

$点赞，你的认可是我创作的动力！$

$收藏，你的青睐是我努力的方向！$

$评论，你的意见是我进步的财富！$