【小Y学算法】⚡️每日LeetCode打卡⚡️——27.对称二叉树

📢前言 🚀 算法题 🚀

• 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
• 🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
• 🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
• 🌲 今天是力扣算法题持续打卡第27天🎈！

🚀 算法题 🚀 🌲原题样例

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树[1,2,2,3,4,4,3]是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3]则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

🌻C#方法：递归

思路解析

递归，通常来说一个问题可以分为多个子问题去解决&&问题和求解过程和子问题的求解过程一致&&存在递归终止条件，满足这三个条件就适合用递归。

直接看题目例子的话比较容易发现，镜像对称就是二叉树每层是中心对称的。

所以可以从顶层递归看每层是否是这样的中心对称。

代码：

public class Solution {
    static bool func(TreeNode x, TreeNode y) {
        if (x == null) {
            return y == null;
        }

        if (y == null || x.val != y.val) {
            return false;
        }

        return func(x.left, y.right) && func(x.right, y.left);
    }


    public bool IsSymmetric(TreeNode root) {
        return root == null ? true : func(root.left, root.right);
    }
}

执行结果

通过
执行用时：84 ms，在所有 C# 提交中击败了88.89%的用户
内存消耗：24.9 MB，在所有 C# 提交中击败了91.43%的用户

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

🌻Java 方法一：递归

思路解析

代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

执行结果

通过
执行用时：0 ms，在所有 Java  提交中击败了100.00%的用户
内存消耗：36.5 MB，在所有 Java 提交中击败了37.04%的用户

复杂度分析

时间复杂度：O(min(m+n))其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。

空间复杂度：O(min(m+n))其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

🌻Java 方法二：迭代

思路解析

「方法一」中我们用递归的方法实现了对称性的判断，那么如何用迭代的方法实现呢？首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。

初始化时我们把根节点入队两次。

每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。

当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1