One Pass DFS Java solution

  • 0

    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
    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){
            return map.get(node);

Log in to reply

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