forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathimgolden77.py
More file actions
33 lines (24 loc) · 935 Bytes
/
imgolden77.py
File metadata and controls
33 lines (24 loc) · 935 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
29
30
31
32
"""
# 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 Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return None
old_to_new = {}
def dfs(curr_node):
if curr_node in old_to_new:
return old_to_new[curr_node]
copy = Node(curr_node.val)
old_to_new[curr_node] = copy
for neighbors in curr_node.neighbors:
copy.neighbors.append(dfs(neighbors))
return copy
return dfs(node)
# O(N+E) time complexity where N is the number of nodes and E is the number of edges in the graph.
# O(N) space complexity for the hashmap and the recursion stack in the worst case.