| 🚀 算法题 🚀 |
- 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
- 🌲 提示：本专栏解题 编程语言一律使用 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
思路解析
递归，通常来说一个问题可以分为多个子问题去解决&&问题和求解过程和子问题的求解过程一致&&存在递归终止条件，满足这三个条件就适合用递归。
直接看题目例子的话比较容易发现，镜像对称就是二叉树每层是中心对称的。
所以可以从顶层递归看每层是否是这样的中心对称。
代码：
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)
思路解析
代码：
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 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
思路解析
「方法一」中我们用递归的方法实现了对称性的判断，那么如何用迭代的方法实现呢？首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。
初始化时我们把根节点入队两次。
每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。
当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
代码：
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 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
}
执行结果
通过
执行用时：1 ms，在所有 Java 提交中击败了23.81%的用户
内存消耗：37.8 MB，在所有 Java 提交中击败了7.81%的用户
复杂度分析
时间复杂度：O()
空间复杂度：O(n)
C#和 Java 两种编程语言进行解题联系客服
