Clone Graph

Medium

Python

def clone_graph(node):
    if not node: return None
    visited={}
    def clone(n):
        if n in visited: return visited[n]
        copy=type('Node',(),{'val':n.val,'neighbors':[]})()
        visited[n]=copy
        for nb in n.neighbors:
            copy.neighbors.append(clone(nb))
        return copy
    return clone(node)

Java

public Node cloneGraph(Node node){
    if(node==null) return null;
    Map<Node,Node> visited=new HashMap<>();
    return clone(node,visited);
}
Node clone(Node n,Map<Node,Node> visited){
    if(visited.containsKey(n)) return visited.get(n);
    Node copy=new Node(n.val);
    visited.put(n,copy);
    for(Node nb:n.neighbors) copy.neighbors.add(clone(nb,visited));
    return copy;
}

Key Insight

Python closure captures visited. Java passes as parameter. Memo pattern identical.

Python → Java Differences

Nested function captures visited
Java passes map as param
DFS clone with memo identical

Python

def clone_graph(node):
    if not node: return None
    visited={}
    def clone(n):
        if n in visited: return visited[n]
        copy=type('Node',(),{'val':n.val,'neighbors':[]})()
        visited[n]=copy
        for nb in n.neighbors:
            copy.neighbors.append(clone(nb))
        return copy
    return clone(node)

Java

public Node cloneGraph(Node node){
    if(node==null) return null;
    Map<Node,Node> visited=new HashMap<>();
    return clone(node,visited);
}
Node clone(Node n,Map<Node,Node> visited){
    if(visited.containsKey(n)) return visited.get(n);
    Node copy=new Node(n.val);
    visited.put(n,copy);
    for(Node nb:n.neighbors) copy.neighbors.add(clone(nb,visited));
    return copy;
}

Algorithm Steps

1. DFS with visited map
2. Clone before recursing

← Previous All Graphs Next →