```
# DFS + stack
class Solution(object):
def isSameTree(self, p, q):
stack = [(q, p)]
while stack:
n1, n2 = stack.pop()
if n1 and n2:
if n1.val != n2.val:
return False
stack += [(n1.right, n2.right), (n1.left, n2.left)]
elif n1 or n2:
return False
else:
continue
return True
# BFS + queue
class SolutionBFS(object):
def isSameTree(self, p, q):
queue = [(p, q)]
while queue:
n1, n2 = queue.pop(0)
if n1 and n2:
if n1.val != n2.val:
return False
# put 2 lefts, 2 rights, order doesn't matter
queue += [(n1.left, n2.left), (n1.right, n2.right)]
elif n1 or n2:
return False
else:
continue
return True
# Recursive
class SolutionRecursive(object):
def isSameTree(self, p, q):
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p == q
```