解法一：递归

对称二叉树问题可以转换为left, right两个树是否为镜像问题。镜像需要满足的条件是：

  1. left与right同时为空，或同时不为空且值相同；
  2. left的左子树与right的右子树镜像并且left的右子树与right左子树是镜像。

问题入口即变成root与root是否为镜像，即自己与自己是否镜像。一个对称二叉树一定自己与自己也是镜像。

  1. class Solution:
  2.     def isSymmetric(self, root: TreeNode) -> bool:
  3.         def check(left: TreeNode, right: TreeNode) -> bool:
  4.             if not left and not right:
  5.                 return True
  6.             if not left or not right:
  7.                 return False
  8.             if left.val != right.val:
  9.                 return False
  10.             return check(left.left, right.right) and check(left.right, right.left)
  11.         return check(root, root)

解法二：同步BFS

用一个队列，将两棵树的镜像遍历节点按顺序加入队列，同步BFS的过程中判断节点是否为空（均为空、一个为空）、都不为空的情况下值是否相等。

  1. class Solution:
  2.     def isSymmetric(self, root: TreeNode) -> bool:
  3.         def check(left: TreeNode, right: TreeNode) -> bool:
  4.             queue = [left, right]
  5.             while queue:
  6.                 left = queue.pop(0)
  7.                 right = queue.pop(0)
  8.                 if not left and not right:
  9.                     # 注意这里是continue，应为迭代法需要迭代完成没有返回False才表示镜像
  10.                     continue
  11.                 if not left or not right:
  12.                     return False
  13.                 if left.val != right.val:
  14.                     return False
  15.                    queue.extend([left.left, right.right, left.right, right.left])
  16.             # 迭代完成，确认镜像
  17.             return True
  18.         return check(root, root)

同类题

100. 相同的树

递归

  1. class Solution:
  2.     def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
  3.         if not p and not q:
  4.             return True
  5.         if not p or not q:
  6.             return False
  7.         return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

迭代和对称二叉树也差不多。