Problem Description
Given the roots of two binary trees p and q, 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:
p = [1,2,3], q = [1,2,3] - Output:
True
Example 2:
- Input:
p = [1,2], q = [1,null,2] - Output:
False
Example 3:
- Input:
p = [1,2,1], q = [1,1,2] - Output:
False
My Idea
My idea here was to modify the algorithm from 104. Maximum Depth Of Binary Tree, so it traverses both trees simultaneously and compares each node. This allows us to achieve a time complexity of O(min(n,m)).
My solution
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Time Complexity: O(min(n,m))
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if (not p and q) or (not q and p):
return False
if p.val == q.val:
return True and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
else:
return False