forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path8804who.py
More file actions
33 lines (27 loc) · 964 Bytes
/
8804who.py
File metadata and controls
33 lines (27 loc) · 964 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
"""
# 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
visited = {}
new_node = Node()
def dfs(original_node, new_node):
if original_node.val in visited:
return
visited[original_node.val] = new_node
new_node.val = original_node.val
new_node.neighbors = []
for neighbor in original_node.neighbors:
new_node.neighbors.append(Node())
if neighbor.val not in visited:
dfs(neighbor, new_node.neighbors[-1])
new_node.neighbors[-1] = visited[neighbor.val]
dfs(node, new_node)
return new_node