Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
/ \       / \
2   3     2   3

[1,2,3],   [1,2,3]

Output: true


Example 2:

Input:     1         1
/           \
2             2

[1,2],     [1,null,2]

Output: false


Example 3:

Input:     1         1
/ \       / \
2   1     1   2

[1,2,1],   [1,1,2]

Output: false


## Solutions

### 1. 递归

# Time Complexity: O(logn)
# Space Complexity: O(1)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return p == q
# Runtime: 40 ms, faster than 39.43% of Python3 online submissions for Same Tree.
# Memory Usage: 13.6 MB, less than 5.72% of Python3 online submissions for Same Tree.


### 2. DFS-迭代/递推

# Time Complexity: O(logn)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
stack = [(p, q)]
while stack:
node1, node2 = stack.pop()
if not node1 and not node2:
continue
elif None in [node1, node2]:
return False
else:
if node1.val != node2.val:
return False
stack.append((node1.right, node2.right))
stack.append((node1.left, node2.left))
return True
# Runtime: 36 ms, faster than 74.66% of Python3 online submissions for Same Tree.
# Memory Usage: 13.7 MB, less than 5.72% of Python3 online submissions for Same Tree.


### 3. BFS

# Time Complexity: O(logn)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
queue = [(p, q)]
while queue:
node1, node2 = queue.pop(0)
if not node1 and not node2:
continue
elif None in [node1, node2]:
return False
else:
if node1.val != node2.val:
return False
queue.append((node1.left, node2.left))
queue.append((node1.right, node2.right))
return True
# Runtime: 32 ms, faster than 92.92% of Python3 online submissions for Same Tree.
# Memory Usage: 13.8 MB, less than 5.72% of Python3 online submissions for Same Tree.