forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhi-rachel.py
More file actions
60 lines (48 loc) Β· 1.55 KB
/
hi-rachel.py
File metadata and controls
60 lines (48 loc) Β· 1.55 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
59
60
"""
무방ν₯ μ°κ²°λ λ
Έλ
κ·Έλνμ κΉμ λ³΅μ¬ λ°νν΄λΌ
TC: O(V + E), V: λ
Έλμ μ, E: μ΄μμ μ
SC: O(V + E)
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
# κΉμ΄ μ°μ νμ νμ΄
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return
clones = {}
def dfs(node):
if node in clones:
return clones[node]
clone = Node(node.val)
clones[node] = clone
for nei in node.neighbors:
clone.neighbors.append(dfs(nei))
return clone
return dfs(node)
from collections import deque
# λμ΄ μ°μ νμ νμ΄
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return
clone = Node(node.val)
clones = {node: clone}
queue = deque([node])
while queue:
node = queue.popleft()
for nei in node.neighbors:
if nei not in clones:
clones[nei] = Node(nei.val)
queue.append(nei)
clones[node].neighbors.append(clones[nei])
return clone