forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyolophg.py
More file actions
19 lines (15 loc) · 815 Bytes
/
yolophg.py
File metadata and controls
19 lines (15 loc) · 815 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Time Complexity: O(N) - visit each node once.
# Space Complexity: O(N) in the worst case (skewed tree), O(log N) in the best case (balanced tree).
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# if both trees are empty, they are obviously the same
if p is None and q is None:
return True
# if one tree is empty but the other is not, they can't be the same
if p is None or q is None:
return False
# if values of the current nodes are different, trees are not the same
if p.val != q.val:
return False
# recursively check both left and right subtrees
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)