Depth First Simple Java Solution


  • 97
    M
    public class Solution {
        private HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            return clone(node);
        }
    
        private UndirectedGraphNode clone(UndirectedGraphNode node) {
            if (node == null) return null;
            
            if (map.containsKey(node.label)) {
                return map.get(node.label);
            }
            UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
            map.put(clone.label, clone);
            for (UndirectedGraphNode neighbor : node.neighbors) {
                clone.neighbors.add(clone(neighbor));
            }
            return clone;
        }
    }

  • 16
    C

    can this approach handle the case that there are nodes having the same label value in a cycle?. I think it might be better to use the HashMap<UndirectedGraphNode, UndirectedGraphNode>


  • 0
    S

    Very good solution. It can be written inside just one method as well.


  • 30

    As @san89kalp said, it can be written in just one method.

    public HashMap<Integer, UndirectedGraphNode> map = new HashMap();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        if (map.containsKey(node.label)) 
            return map.get(node.label);
        UndirectedGraphNode cloned = new UndirectedGraphNode(node.label);
        map.put(cloned.label, cloned);
        for(UndirectedGraphNode neighbor: node.neighbors){
            cloned.neighbors.add(cloneGraph(neighbor));
        }
        return cloned;
    }

  • 1

    @ chenw2000, by putting this line map.put(clone.label, clone); before for loop makes sure cycle can be detected.


  • 40

    I think it is better not to use global hashmap in practice. Here is my more general solution.

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        HashMap<Integer,UndirectedGraphNode> map = new HashMap<Integer,UndirectedGraphNode>();
        return dfs(node,map);
    }
    private UndirectedGraphNode dfs(UndirectedGraphNode node, HashMap<Integer,UndirectedGraphNode> map) {
        if (node == null) return null;
        if (map.containsKey(node.label)) {
            return map.get(node.label);
        } else {
            UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
            map.put(node.label,clone);
            for (int i = 0; i < node.neighbors.size(); i++) {
                clone.neighbors.add(dfs(node.neighbors.get(i), map));
            }
            return clone;
        }
    }

  • 8
    H

    clone is key word, we'd better not define key word as variable.


  • 0
    V

    I think we can get rid of the helper function because the map is global :) https://leetcode.com/discuss/91813/without-helper-function-java-dfs-simple-solution


  • 2
    Y

    Another implementation based on your idea, just a few changes. Map is defined as local variable instead of global, used Map<> instead of HashMap<> to be more generic.

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<Integer, UndirectedGraphNode> map = new HashMap<>();
        return dfs(node, map);
    }
    
    private UndirectedGraphNode dfs(UndirectedGraphNode node, Map<Integer, UndirectedGraphNode> map) {
        if(node == null) {
            return null;
        }
        if(map.containsKey(node.label)) {
            return map.get(node.label);
        }
        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        map.put(node.label, clone);
        for(UndirectedGraphNode next : node.neighbors) {
            clone.neighbors.add(dfs(next, map));
        }
        return clone;
    }

  • 0
    K
    This post is deleted!

  • -1
    K
    This post is deleted!

  • 1
    Q

    As @keran.yang.5 said, by this way, you cannot recursively invoke the function clone().


  • 6
    L

    Nice! Here's another quick variation, saves a few recursive calls:

    public class Solution {
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            return cloneGraph(node, new HashMap<UndirectedGraphNode, UndirectedGraphNode>());
        }
        
        private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> cloneMap) {
            if (node == null) return null;
            UndirectedGraphNode cloned = new UndirectedGraphNode(node.label);
            cloneMap.put(node, cloned); // visited = true;
            for(UndirectedGraphNode neighbor: node.neighbors){
                if (cloneMap.containsKey(neighbor)) { // if we have already explored this vertex grab its clone from map
                    cloned.neighbors.add(cloneMap.get(neighbor));
                } else { // explore unvisited vertex
                    cloned.neighbors.add(cloneGraph(neighbor, cloneMap));
                }
            }
            return cloned;
        }
    }
    

  • 1
    B

    I want to know if the label is key word? if not, should use HashMap<UndirectedGraphNode,UndirectedGraphNode>


  • 0
    A
    This post is deleted!

  • 1

    @levani Same idea as yours by passing Map as method argument. Since "Nodes are labeled uniquely", I choose label as key. Thanks for sharing!

        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (node == null) return null;
            return dfs(node, new HashMap<>());
        }
    
        private UndirectedGraphNode dfs(UndirectedGraphNode node,
                                        Map<Integer,UndirectedGraphNode> copies) {
            if (copies.containsKey(node.label)) return copies.get(node.label);
    
            UndirectedGraphNode cpy = new UndirectedGraphNode(node.label);
            copies.put(cpy.label, cpy);
    
            for (UndirectedGraphNode n : node.neighbors)
                cpy.neighbors.add(dfs(n, copies));
            return cpy;
        }
    

  • 0
    B

    @levani I have the same idea. It is easy to read.
    my code


  • 1
    I

    @levani said in Depth First Simple Java Solution:

    HashMap<UndirectedGraphNode, UndirectedGraphNode>()

    I vote the method with HashMap<UndirectedGraphNode, UndirectedGraphNode>() since it can handle the situation that two nodes with the same label value.


  • 0

    Nice solution!

    My slight variations:

    • Only check for null in the initial call
    • Do not use global hash map
    • map node to cloned node instead of label to cloned node in case of duplicate labels
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        return cloneGraph(node, new HashMap<>());
    }
    
    private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> visited) {
        if (visited.containsKey(node)) return visited.get(node);
        
        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        
        visited.put(node, clone);
        
        for (UndirectedGraphNode neighbor : node.neighbors)
            clone.neighbors.add(cloneGraph(neighbor, visited));
        
        return clone;
    }
    

  • 0

    This question is the same as copy list with random pointer.

    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap();
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (node == null) return null;
            
            if (map.containsKey(node)) return map.get(node);
            
            UndirectedGraphNode myNode = new UndirectedGraphNode(node.label);
            map.put(node, myNode);
            
            for (UndirectedGraphNode n : node.neighbors) {
                myNode.neighbors.add(cloneGraph(n));
            }
            return myNode;
        }
    

Log in to reply
 

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