class Solution: def isSymmetric(self, root: TreeNode) -> bool: def recur(L, R): if not L and not R: return True if not L or not R or L.val != R.val: return False return recur(L.left, R.right) and recur(L.right, R.left) return recur(root.left, root.right) if root else True
如果上面的不容易理解,可以看下面的
# 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 recur(L, R): if not L and not R: return True if not L or not R or L.val != R.val: return False return recur(L.left, R.right) and recur(L.right, R.left) return recur(root.left, root.right)
迭代 class Solution: def isSymmetric(self, root: TreeNode) -> bool: if root is None: return True q = [] q.append(root.left) q.append(root.right) while len(q)!=0: A = q.pop(0) B = q.pop(0) if A == None and B == None: continue if A == None or B == None: return False if A.val != B.val: return False q.append(A.left) q.append(B.right) q.append(A.right) q.append(B.left) return True
将上一题。改进:
class Solution: def isSymmetric_queue(self, root: TreeNode) -> bool: """ 辅助队列法 """ if not root: return True queue = [(root.left,root.right)] while queue: l, r = queue.pop(0) if not l and not r: # 如果左右子节点为空,跳过后面步骤 continue if not l or not r: # 如果左右子节点任意一个为空,则表示不对称 return False if l.val != r.val: # 如果左右子节点的值不等,则表示不对称 return False queue.append((l.left, r.right)) # 将左子树的左节点,和右子树的右节点放入队列 queue.append((l.right, r.left)) return True