forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsocow.py
More file actions
58 lines (45 loc) · 1.32 KB
/
socow.py
File metadata and controls
58 lines (45 loc) · 1.32 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
"""
100. Same Tree
문제 요약
- 두 이진 트리가 똑같은지 확인하기
- 구조도 같고, 값도 같아야 True
문제 예시
트리1: 트리2:
1 1
/ \ / \
2 3 2 3
→ True (완전 동일!)
트리1: 트리2:
1 1
/ \
2 2
→ False (구조가 다름!)
핵심 알고리즘
- 패턴: 재귀 (DFS)
- 시간복잡도: O(n) - 모든 노드 방문
- 공간복잡도: O(h) - h는 트리 높이
핵심 아이디어
1. 둘 다 None → True
2. 하나만 None → False
3. 값이 다름 → False
4. 왼쪽 서브트리 비교 & 오른쪽 서브트리 비교
"""
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# 둘 다 None → 같음!
if not p and not q:
return True
# 하나만 None → 다름!
if not p or not q:
return False
# 값이 다름 → 다름!
if p.val != q.val:
return False
# 왼쪽끼리 비교 AND 오른쪽끼리 비교
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)