forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathwozlsla.py
More file actions
49 lines (38 loc) · 1.16 KB
/
wozlsla.py
File metadata and controls
49 lines (38 loc) · 1.16 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
from typing import Optional
"""
# Intuition
어떻게 순서가 정의되지?
순회 -> 어떤 구조?
비교
# Approach
트리가 동일하려면 ?
1. 구조 비교
2. 값 비교
트리 동시 탐색
- 두 노드가 모두 null (구조) -> True
- 둘 중 하나만 null (구조) -> False
- 두 노드가 모두 값이 있음 (값) -> True/False
# Complexity
시간 복잡도
- O(N)
공간 복잡도
- (재귀) 전위 순회: 콜 스택 -> O(H)
"""
# 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
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# 종결 조건 1: 두 노드가 모두 null이면 구조가 동일함
if p is None and q is None:
return True
# 종료 조건 2:
# - 구조 불일치
# - 값 불일치
if p is None or q is None or p.val != q.val:
return False
# (재귀) 자식 비교
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)