One Pass DFS Java solution


  • 0
    N

    My initial thought is to DFS through the graph and build the <old node, new node> map, then DFS through the graph again to populate the neighbors list for new nodes.

    On a second thought we could just do one round of DFS, if we return the new node pointer.

    Just realize this is basically the same with https://discuss.leetcode.com/topic/9629/depth-first-simple-java-solution
    And also just realize we can assume labels are unique.. But anyway, this will work.

    public class Solution {
        
        private Map<UndirectedGraphNode,UndirectedGraphNode> map;
    
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if(node == null) return null;
            
            map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
            return DFS(node);
        }
        
        // returns the mapped one
        public UndirectedGraphNode DFS(UndirectedGraphNode node){
            if(node == null) return null;
            if(map.containsKey(node)) return map.get(node); // if already traversed. 
        
            map.put(node, new UndirectedGraphNode(node.label));
            for(UndirectedGraphNode neighbor : node.neighbors){
                map.get(node).neighbors.add(DFS(neighbor));
            }
            
            return map.get(node);
        }
    }
    

Log in to reply
 

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