Depth First First Solution - 4 ms Runtime.


  • 0
    S

    Basically, the idea is to traverse the original graph using DFS and add cloned nodes whenever we come across something new. In the event that we run across an original graph node that we have already seen, then we return the clone that is already associated with it.

    /**
     * Definition for undirected graph.
     * class UndirectedGraphNode {
     *     int label;
     *     List<UndirectedGraphNode> neighbors;
     *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
     * };
     */
    public class Solution {
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (node == null) return node;
            
            Map<UndirectedGraphNode, UndirectedGraphNode> visited = new HashMap<>();
            
            return cloneGraph(visited, node);
        }
        
        private UndirectedGraphNode cloneGraph(Map<UndirectedGraphNode, UndirectedGraphNode> visited, UndirectedGraphNode node) {
            if (visited.containsKey(node)) return visited.get(node);
            
            UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
            visited.put(node, clone);
            
            for (UndirectedGraphNode edge : node.neighbors) {
                clone.neighbors.add(cloneGraph(visited, edge));
            }
            
            return clone;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.