101. 对称二叉树
https://leetcode-cn.com/problems/symmetric-tree/
解法一:递归
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def helper(t1, t2): #辅助函数
if not t1 and not t2: #都为空
return True
elif not t1 or not t2: #只有一个为空
return False
else: #都不为空
if t1.val == t2.val:
#分别反向访问t1,t2的左右子树
return helper(t1.left, t2.right) and helper(t1.right, t2.left)
else:
return False
return helper(root, root) #都从根开始
解法二:层序
分别对该树进行从左到右和从右到左的层序遍历,每次分别比较取出的结点,不相等则false
import queue
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
q = queue.Queue()
q.put(root)
q.put(root)
#并不是严格的层序,每轮只取两个结点
#分别表示从左到右和从右到左的遍历顺序
while q.qsize() > 0:
t1 = q.get()
t2 = q.get()
if t1 == None and t2 == None:
continue
elif t1 == None or t2 == None:
return False
elif t1.val != t2.val:
return False
#t1的左右入队顺序无所谓,关键是t1要和t2对应上
#t1取左,t2对应就要取右,反之亦然
q.put(t1.left)
q.put(t2.right)
q.put(t1.right)
q.put(t2.left)
return True
最后更新于