【算法训练-二叉树 四】【对称与翻转】对称二叉树、翻转二叉树

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【二叉树的形态变化】，使用【二叉树】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

对称二叉树【EASY】

对称二叉树的判断

题干

解题思路

对称，就是左右两边相等，也就是左子树和右子树是相当的注意这句话，左子树和右子相等，也就是说要递归的比较左子树和右子树。
我们将根节点的左子树记做 left，右子树记做 right。

• 比较 left 是否等于 right，不等的话直接返回就可以了。
• 如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点
  比如看下面这两个子树(他们分别是根节点的左子树和右子树)，能观察到这么一个规律

• 终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
• 返回值： 每一级将子问题是否匹配的结果往上传递。
• 本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称

代码实现

给出代码实现基本档案

基本数据结构：二叉树
辅助数据结构：无
算法：递归、DFS
技巧：无

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

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 bool布尔型
     */
    public boolean isSymmetrical (TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        return dfsCheck(pRoot.left, pRoot.right);
    }

    private boolean dfsCheck(TreeNode left, TreeNode right) {
        // 1 递归终止条件：如果左右子节点都为null，说明到达叶子节点，终止且为true
        if (left == null && right == null) {
            return true;
        }

        // 2 本级判断依据：如果两个节点其中一个为null则不对称
        if (left == null || right == null) {
            return false;
        }
        // 3 本级判断依据：如果两个节点值不相等，则不对称
        if (left.val != right.val) {
            return false;
        }

        // 4 继续进入下级做判断
        return dfsCheck(left.right, right.left) && dfsCheck(left.left, right.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
42
43
44
45
46
47

复杂度分析

时间复杂度：O(n)，其中n为二叉树的节点数，遍历整棵二叉树
空间复杂度：O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为n

翻转二叉树【EASY】

和对称二叉树类似，只不过对称二叉树是判断，翻转二叉树是做节点位移

题干

解题思路

其实就是交换一下左右节点，然后再递归的交换左节点，右节点我们可以总结出递归的两个条件如下：

• 终止条件：当前节点为 null 时返回
• 交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点

深度优先遍历。

代码实现

给出代码实现基本档案

基本数据结构：二叉树
辅助数据结构：无
算法：递归，DFS
技巧：无

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

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;
        }
        dfsChange(pRoot);
        return pRoot;

    }

    private TreeNode dfsChange(TreeNode node) {
        // 1 递归终止条件：节点为null
        if (node == null) {
            return null;
        }

        // 2 本级任务，交换 左右子树
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        // 3 递归交换左右子树内部结构
        dfsChange(node.left);
        dfsChange(node.right);

        return node;
    }
}
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
48

复杂度分析

时间复杂度：遍历了整棵树节点，时间复杂度为O（N）
空间复杂度：极端情况下，二叉树退化为链表，递归栈的深度为O（N），空间复杂度为O（N）