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.