每日一道 LeetCode (21)：对称二叉树
共 2433字，需浏览 5分钟
·
2020-08-18 11:57
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：对称二叉树
题目来源：https://leetcode-cn.com/problems/symmetric-tree/
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
解题思路
LeetCode 题的顺序蛮有意思的么，还按照数据结构来，先是数组，然后是列表，接着是链表，现在轮到的二叉树，已经连续两天是二叉树了，这是怕我们一道题学不会还带强化练习一下的么。。。
今天这道题和昨天那道题从解法上来讲有点像，都是两种方案，递归和迭代，看来处理二叉树的问题，一般都会使用到这两种手段。
至于这道题的解法，emmmmmmmmmmmmmmmm......
原谅我做题少，直接翻开了参考答案。
这道题的核心在于，如何判断一个二叉树是对称二叉树？
我看到官方解法把这个问题转化了一下，转化成下面这样：
嗯，没问题，确实是这样的，竟然如此简单。
可我为啥就是想不到呢？
菜就是做题少，多做点题就知道了。
解题方案一：递归
递归的思路很简单，同步的移动两个指针，一个向左移动，另一个向右移动，比较这两个指针指向的元素是否相等。
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);
}
解题方案二：迭代
昨天的那道题，我们使用了两个队列，分别来存放两个二叉树进行比较，今天这道题一样可以使用两个队列进行操作，只是需要一个队列先放入左子树，另一个队列先放入右子树。
public boolean check_2(TreeNode p, TreeNode q) {
Queue queue1 = new LinkedList<>();
Queue queue2 = new LinkedList<>();
queue1.offer(p);
queue2.offer(q);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
TreeNode node1 = queue1.poll();
TreeNode node2 = queue2.poll();
if (node1 == null && node2 == null) continue;
if ((node1 == null || node2 == null) || (node1.val != node2.val)) return false;
queue1.offer(node1.left);
queue1.offer(node1.right);
queue2.offer(node2.right);
queue2.offer(node2.left);
}
return true;
}
这个方案稍有不足，就是我们使用了两个队列，实际上在答案中给出的方案是使用一个队列就可以完成的。
初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。
public boolean check_1(TreeNode p, TreeNode q) {
Queue queue = new LinkedList<>();
queue.offer(p);
queue.offer(q);
while (!queue.isEmpty()) {
p = queue.poll();
q = queue.poll();
if (p == null && q == null) continue;
if ((p == null || q == null) || (p.val != q.val)) return false;
queue.offer(p.left);
queue.offer(q.right);
queue.offer(p.right);
queue.offer(q.left);
}
return true;
}
这两种方案，耗时都是一致的，时间复杂度都是 O(n) 。
