题目描述
给定一个二叉树，检查它是否是镜像对称的。
递归解法
以 t1、t2 表示二叉树的左子树和右子树，若 t1 与 t2 对称，则二叉树对称；若 t1 的根节点值与 t2 的根节点值相等，且 t1 的左子树与 t2 的右子树对称，且 t1 的右子树与 t2 的左子树对称，则 t1 与 t2 对称；......；以 t1_n、t2_n 表示 t1、t2 的某一阶段的子树，若 t1_n 的根节点值与 t2_n 的根节点值相等，且 t1_n 的左子树与 t2_n 的右子树对称，且 t1_n 的右子树与 t2_n 的左子树对称，则 t1_n 与 t2_n 对称。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
return self.compare(root.left,root.right)
def compare(self,node1,node2):
if not node1 and not node2:
return True
if node1 and node2 and node1.val==node2.val:
return self.compare(node1.left,node2.right) and self.compare(node1.right,node2.left)
return False
迭代解法
以队列形式存储 t1_n 节点的右子节点与 t2_n 节点的左子节点，同时存储 t1_n 节点的左子节点与 t2_n 节点的右子节点，两两比较，节点不同则不是对称子树。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
arr=[root,root]
while len(arr)>0:
node1,node2=arr.pop(0),arr.pop(0)
if not node1 and not node1:
continue
if node1 and node2 and node1.val==node2.val:
arr.append(node1.right)
arr.append(node2.left)
arr.append(node1.left)
arr.append(node2.right)
else:
return False
return True
