描述
给定二叉树，返回它是否是自身的镜像（即这棵二叉树是否对称）。
在线评测地址：领扣题库官网
样例1
输入: {1,2,2,3,4,4,3}
输出: true
解释:
1
/ \
2 2
/ \ / \
3 4 4 3
{1,2,2,3,4,4,3}这棵二叉树是对称的样例2
输入: {1,2,2,#,3,#,3}
输出: false
解释:
1
/ \
2 2
\ \
3 3
很显然这棵二叉树并不对称用递归和迭代的方法来解决这个问题(2种解法)
代码
使用分治法 Divide Conquer 的版本
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, Noneclass Solution:
@param root: root of the given tree
@return: whether it is a mirror of itself
"""
def isSymmetric(self, root):
if not root:
return True
return self._is_symmetric(root.left, root.right)
def _is_symmetric(self, left_root, right_root):
if left_root is None and right_root is None:
return True
if left_root is None or right_root is None:
return False
if left_root.val != right_root.val:
return False
left = self._is_symmetric(left_root.left, right_root.right)
right = self._is_symmetric(left_root.right, right_root.left)
return left and right使用Iteration的版本
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, Noneclass Solution:
@param root: root of the given tree
@return: whether it is a mirror of itself
"""
def isSymmetric(self, root):
inorder = self.inorder(root, reverse=False)
reverse_inorder = self.inorder(root, reverse=True)
if inorder != reverse_inorder:
return False
preorder = self.preorder(root, reverse=False)
reverse_preorder = self.preorder(root, reverse=True)
return preorder == reverse_preorder
def get_left(self, node, reverse):
if reverse:
return node.right
return node.left
def get_right(self, node, reverse):
if reverse:
return node.left
return node.right
def preorder(self, root, reverse):
stack = [root]
order = []
while stack:
node = stack.pop()
order.append(node.val)
right = self.get_right(node, reverse)
if right:
stack.append(right)
left = self.get_left(node, reverse)
if left:
stack.append(left)
return order
def inorder(self, root, reverse):
stack = []
while root is not None:
stack.append(root)
root = self.get_left(root, reverse)
order = []
while stack:
node = stack[-1]
order.append(node.val)
right = self.get_right(node, reverse)
if right is not None:
node = right
while node is not None:
stack.append(node)
node = self.get_left(node, reverse)
else:
stack.pop()
while stack and self.get_right(stack[-1], reverse) == node:
node = stack.pop()
return order使用 BFS 算法的版本
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, Noneclass Solution:
@param root: root of the given tree
@return: whether it is a mirror of itself
"""
def isSymmetric(self, root):
queue = [root]
while queue:
next_queue = []
for i in range(len(queue)):
if queue[i] is None:
continue
next_queue.append(queue[i].left)
next_queue.append(queue[i].right)
if not self.is_mirror(next_queue):
return False
queue = next_queue
return True
def is_mirror(self, queue):
left, right = 0, len(queue) - 1
while left < right:
if not self.is_same(queue[left], queue[right]):
return False
left, right = left + 1, right - 1
return True
def is_same(self, node1, node2):
if node1 and node2:
return node1.val == node2.val
return node1 is None and node2 is None更多题解参考：九章官网solution
