LeetCode刷题DAY 26：对称二叉树
难度：简单 关键词：DFS、BFS
⭐️⭐️⭐️
1
题目描述
给定一个二叉树，判断是否为镜像对称。如输入[1,2,2,3,4,4,3]返回True。
2
题解
在LeetCode刷题DAY 15：二叉树的层序遍历一文中介绍了BFS和DFS，这里不赘述直接看代码。
思路一：BFS
将节点压入队列中，依次弹出要比较的节点。此处要注意的是，因为是求镜像对称，某一节点的左子树要与对称节点的右子树比较，因此要注意节点压入队列中的顺序。且要注意空树也是对称的这一特殊情况。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
queue = [root.left,root.right]
while queue:
root_left = queue.pop()
root_right = queue.pop()
if root_left == None and root_right == None:
continue
if root_left == None or root_right == None:
return False
if root_left.val != root_right.val:
return False
#此处注意压入节点的顺序
queue.extend([root_left.left,root_right.right,root_left.right,root_right.left])
return True思路二：DFS
如果两棵树跟节点值相同，且一棵树的左子树与另一棵的右子树对称，则两棵树对称。因此根据这个规则通过递归进行判断。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
def isMirror(root1,root2):
if root1 == None or root2 == None:
return False
if root1.val != root2.val:
return False
if root1 == None and root2 == None:
return True
return isMirror(root1.left,root2.right) and isMirror(root1.right,root2.left)
return isMirror(root.left,root.right)本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读