刷题小组|倒计时9天：对称二叉树
题目
今天的题目是：对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
3241423
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
23123
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
请大家独立思考并完成，欢迎在刷题小组交流群中讨论学习。
大家加油！
（以下内容先别看！）
解题思路（递归）
一般来说，涉及到二叉树的问题，我们可以从递归、迭代以及前中后遍历的顺序来考虑。
首先看递归的思想：
如果一颗镜像二叉树，其左右子树都是镜像二叉树吗？
仔细想一想，实际不是的。比如下面这个例子：
首先它是一颗镜像二叉树，其左子树（红）和右子树（黄）是对称的；但是左子树本身并不是镜像二叉树，因为左子树的左子树（蓝）和右子树（绿）不是对称的；但是左子树的左子树（蓝）和右子树的右子树镜像对称。
因此，一颗镜像二叉树应当满足如下条件：
-
其左右子树的根节点值相同 -
其左子树的左子树与右子树的右子树镜像对称；其左子树的右子树与右子树的左子树镜像对称
我们将根节点root的左子树记为left，右子树记为right。基于这样的条件，我们使用递归，则：
-
终止条件：left.val != right.val不为镜像；或者left与right都为空则返回True；或者left与right中有一个为空则返回False -
如何递归：递归的比较left.left和right.right；递归的比较left.right和right.left
class Solution(object):
def isSymmetric(self, root):
if not root: return True
def dfs(left, right):
if not (left or right): return True
if not (left and right): return False
if left.val != right.val: return False
return dfs(left.left, right.right) and dfs(left.right, right.left)
return dfs(root.left, root.right)
解题思路（用队列进行迭代）
同样的思路，我们可以用递归解，也可以用迭代解。
用队列来实现，首先从队列中拿出两个节点left和right进行比较，将left.left节点和right.right节点放入队列；将left.right和right.left放入队列。
class Solution(object):
def isSymmetric(self, root):
if not root or not(root.left or root.right):
return True
# 用队列保存节点
queue = [root.left, root.right]
while queue:
# 从队列中取出两个节点并比较是否相等
left = queue.pop(0)
right = queue.pop(0)
# 如果两个节点都为空，就继续循环
if not (left or right): continue
# 如果两者有一个为空就返回false
if not (left and right): return False
if left.val != right.val: return False
# 将左节点的左孩子，右节点的右孩子放入队列
queue.append(left.left)
queue.append(right.right)
# 将左节点的右孩子，右节点的左孩子放入队列
queue.append(left.right)
queue.append(right.left)
return True
解题思路（遍历）
对于一棵镜像二叉树，对这棵树根节点的左子树进行前序遍历: pre_order = [2,3,5,6,4,7,8]；
接着我们对这棵树根节点的右子树进行后序遍历：post_order = [8,7,4,6,5,3,2]
根据两次遍历我们不难发现 post_order 就是 pre_order的逆序，其实这也是对称二叉树的一个性质，根据这一点就不难写出代码了。
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
bli = [] # 用来存左子树的前序遍历
fli = [] # 用来存右子树的后续遍历
if not root: return True
if not (root.left or root.right): return True
if root.left and root.right:
self.pre_order(root.left, bli)
self.post_order(root.right, fli)
fli.reverse()
if bli == fli: return True
else: return False
def pre_order(self, root, li):
if root:
li.append(root.val)
self.pre_order(root.left, li)
self.pre_order(root.right, li)
elif root is None:
li.append(None)
def post_order(self,root,li):
if root:
self.post_order(root.left,li)
self.post_order(root.right,li)
li.append(root.val)
elif root == None:
li.append(None)