LeetCode-Solutions/Python/clone-graph.py at master · pythonpeixun/LeetCode-Solutions · GitHub

27 lines (23 loc) · 848 Bytes

# Time: O(n)

# Space: O(n)

class UndirectedGraphNode(object):

def __init__(self, x):

self.label = x

self.neighbors = []

class Solution(object):

# @param node, a undirected graph node

# @return a undirected graph node

def cloneGraph(self, node):

if node is None:

return None

cloned_node = UndirectedGraphNode(node.label)

cloned, queue = {node:cloned_node}, [node]

while queue:

current = queue.pop()

for neighbor in current.neighbors:

if neighbor not in cloned:

queue.append(neighbor)

cloned_neighbor = UndirectedGraphNode(neighbor.label)

cloned[neighbor] = cloned_neighbor

cloned[current].neighbors.append(cloned[neighbor])

return cloned[node]

Expand file tree