题目描述
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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 复制代码
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
解题思路
递归
对称树实际上就是左子树与右子树镜像对称，那么就可以指定两个指针 l, r 同时反方向移动来遍历这棵树，两个指针开始时都指向根结点，随后 l 右移时，r 左移，l 左移时，r 右移。每次检查当前 l 和 r 节点的值是否相等，左右子树是否对称。
def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ def search(l, r): if not l and not r: return True if not l or not r: return False return l.val == r.val and search(l.left, r.right) and search(l.right, r.left) return search(root, root) 复制代码
- 时间复杂度：O(n)
- 空间复杂度：O(n)
迭代
引入队列是递归-->迭代转换的常用方法。
初始化时我们把根节点 root 入队两次。
每次提取两个结点 p, q 并比较它们的值是否相等（队列中每两个连续的结点应该是相等的），然后将 p, q 结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者从队列中取出的连续结点 p, q 不相等时（树不对称），该算法结束。
def isSymmetric(root): """ :type root: TreeNode :rtype: bool """ if root is None: return False queue = [root, root] while queue: p = queue.pop() q = queue.pop() if not p and not q: continue if not p or not q or p.val != q.val: return False queue.append(p.left) queue.append(q.right) queue.append(p.right) queue.append(q.left) return True 复制代码
- 时间复杂度：O(n)
- 空间复杂度：O(n)
今日打卡完成，目前进度 10/200。
