解法一：递归法

  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)

解法二：迭代法

  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
  8.         queue1 = collections.deque([p])
  9.         queue2 = collections.deque([q])
  11.         while queue1 and queue2:
  12.             node1 = queue1.popleft()
  13.             node2 = queue2.popleft()
  14.             if node1.val != node2.val:
  15.                 return False
  16.             left1, right1 = node1.left, node1.right
  17.             left2, right2 = node2.left, node2.right
  18.             if (not left1) ^ (not left2):
  19.                 return False
  20.             if (not right1) ^ (not right2):
  21.                 return False
  22.             if left1:
  23.                 queue1.append(left1)
  24.             if right1:
  25.                 queue1.append(right1)
  26.             if left2:
  27.                 queue2.append(left2)
  28.             if right2:
  29.                 queue2.append(right2)
  31.         return not queue1 and not queue2