DFS Java Solution Using Map As a Cache


  • 0
    M
    
    public class Solution {
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if(node==null) return node;
            return dfs(node,new HashMap<Integer,UndirectedGraphNode>());
        }
        
        private UndirectedGraphNode dfs (UndirectedGraphNode node, 
                                         Map<Integer,UndirectedGraphNode> cache) {
            
            UndirectedGraphNode clone = cloneNode(node,cache);
            
            for(UndirectedGraphNode neighbor : node.neighbors ) {
                if(!cache.containsKey(neighbor.label)) dfs(neighbor, cache);
                UndirectedGraphNode nClone = cloneNode(neighbor,cache);
                clone.neighbors.add(nClone);
            }
            
            return clone;
        }
        
        private UndirectedGraphNode cloneNode (UndirectedGraphNode node, 
                                           Map<Integer,UndirectedGraphNode> cache) {
            UndirectedGraphNode clone;
            if(cache.containsKey(node.label)) {
                clone = cache.get(node.label);
            } else {
                clone = new UndirectedGraphNode(node.label);
                cache.put(node.label,clone);
            }
            return clone;
        }
    }
    

Log in to reply
 

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