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

&＃x1f4e2;前言

• &＃x1f332; 每天打卡一道算法题&＃xff0c;既是一个学习过程&＃xff0c;又是一个分享的过程&＃x1f61c;
• &＃x1f332; 提示&＃xff1a;本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
• &＃x1f332; 要保持一个每天都在学习的状态&＃xff0c;让我们一起努力成为算法大神吧&＃x1f9d0;&＃xff01;
• &＃x1f332; 今天是力扣算法题持续打卡第27天&＃x1f388;&＃xff01;

&＃x1f332;原题样例

给定一个二叉树&＃xff0c;检查它是否是镜像对称的。

例如&＃xff0c;二叉树[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


&＃x1f33b;C#方法&＃xff1a;递归

思路解析

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

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

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

代码&＃xff1a;

public class Solution {static bool func(TreeNode x, TreeNode y) {if (x &＃61;&＃61; null) {return y &＃61;&＃61; null;}if (y &＃61;&＃61; null || x.val !&＃61; y.val) {return false;}return func(x.left, y.right) && func(x.right, y.left);}public bool IsSymmetric(TreeNode root) {return root &＃61;&＃61; null ? true : func(root.left, root.right);}
}

执行结果

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


复杂度分析

时间复杂度&＃xff1a;O(n)
空间复杂度&＃xff1a;O(n)


&＃x1f33b;Java 方法一&＃xff1a;递归

思路解析

代码&＃xff1a;

class Solution {public boolean isSymmetric(TreeNode root) {return check(root, root);}public boolean check(TreeNode p, TreeNode q) {if (p &＃61;&＃61; null && q &＃61;&＃61; null) {return true;}if (p &＃61;&＃61; null || q &＃61;&＃61; null) {return false;}return p.val &＃61;&＃61; q.val && check(p.left, q.right) && check(p.right, q.left);}
}

执行结果

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


复杂度分析

时间复杂度&＃xff1a;O(min(m&＃43;n))其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索&＃xff0c;只有当两个二叉树中的对应节点都不为空时才会访问到该节点&＃xff0c;因此被访问到的节点数不会超过较小的二叉树的节点数。空间复杂度&＃xff1a;O(min(m&＃43;n))其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数&＃xff0c;递归调用的层数不会超过较小的二叉树的最大高度&＃xff0c;最坏情况下&＃xff0c;二叉树的高度等于节点数。


&＃x1f33b;Java 方法二&＃xff1a;迭代

思路解析

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

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

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

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

代码&＃xff1a;

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 &＃61; 0, p2 &＃61; 0;int[] sorted &＃61; new int[m &＃43; n];int cur;while (p1 < m || p2 < n) {if (p1 &＃61;&＃61; m) {cur &＃61; nums2[p2&＃43;&＃43;];} else if (p2 &＃61;&＃61; n) {cur &＃61; nums1[p1&＃43;&＃43;];} else if (nums1[p1] < nums2[p2]) {cur &＃61; nums1[p1&＃43;&＃43;];} else {cur &＃61; nums2[p2&＃43;&＃43;];}sorted[p1 &＃43; p2 - 1] &＃61; cur;}for (int i &＃61; 0; i !&＃61; m &＃43; n; &＃43;&＃43;i) {nums1[i] &＃61; sorted[i];}}
}


执行结果

通过
执行用时&＃xff1a;1 ms&＃xff0c;在所有 Java 提交中击败了23.81%的用户
内存消耗&＃xff1a;37.8 MB&＃xff0c;在所有 Java 提交中击败了7.81%的用户


复杂度分析

时间复杂度&＃xff1a;O()
空间复杂度&＃xff1a;O(n)


&＃x1f4ac;总结

• 今天是力扣算法题打卡的第二十七天&＃xff01;
• 文章采用 C#和 Java 两种编程语言进行解题
• 一些方法也是参考力扣大神写的&＃xff0c;也是边学习边分享&＃xff0c;再次感谢算法大佬们
• 那今天的算法题分享到此结束啦&＃xff0c;明天再见&＃xff01;
  

&＃x1f680;往期优质文章分享

• ❤️Unity零基础到入门 | 游戏引擎 Unity 从0到1的 系统学习 路线【全面总结-建议收藏】&＃xff01;
• &＃x1f9e1;花一天时间做一个高质量飞机大战游戏&＃xff0c;过万字Unity完整教程&＃xff01;漂亮学妹看了直呼666&＃xff01;
• &＃x1f49b;回忆童年和小伙伴一起玩过的经典游戏【炸弹人小游戏】制作过程&＃43;解析
• &＃x1f49a;通宵一晚做出来的一款类似CS的第一人称射击游戏Demo&＃xff01;原来做游戏也不是很难
• &＃x1f90d;爆肝整整一个周末写一款类似 皇室战争 的 即时战斗类 游戏Demo&＃xff01;两万多字游戏制作过程&＃43;解析&＃xff01;
• &＃x1f499;一款类似“恐龙快打”的 横版街机格斗游戏 该如何制作&＃xff1f;| 一起来学习 顺便送源码【码文不易&＃xff0c;建议收藏学习】
• &＃x1f49c;【超实用技巧】| 提高写文的质量 和 速率必学技能&＃xff1a; Typora 图床配置 详细说明