forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathkayden.py
More file actions
28 lines (22 loc) · 837 Bytes
/
kayden.py
File metadata and controls
28 lines (22 loc) · 837 Bytes
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
from typing import Optional
from collections import deque
class Solution:
# 시간복잡도: O(N) node 개수: N
# 공간복잡도: O(N)
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if node:
visited = {}
copy = Node(val=node.val)
visited[copy.val] = copy
q = deque()
q.append((copy, node))
while q:
cur, node = q.popleft()
for idx, next_node in enumerate(node.neighbors):
if next_node.val not in visited:
new = Node(val=next_node.val)
visited[new.val] = new
q.append((new, next_node))
cur.neighbors.append(visited[next_node.val])
return copy
return node