5ms Java DFS solution with hash map


  • 1
    Y
    public class Solution {
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            //11:15am - 11:26am
            // using hashmap to map orig node to cloned node and check already copied ones (to avoid cyclic copying)
            Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
            return cloneGraphHelper(map, node);
        }
        private UndirectedGraphNode cloneGraphHelper(Map<UndirectedGraphNode, UndirectedGraphNode> map, UndirectedGraphNode node) {
            if (node == null) {
                return null;
            }
            UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
            map.put(node, copy);
            for (UndirectedGraphNode nei : node.neighbors) {
                if (!map.containsKey(nei)) {
                    UndirectedGraphNode neiCopy = cloneGraphHelper(map, nei);
                }
                copy.neighbors.add( map.get(nei) );
            }
            return copy;
        }
    }

Log in to reply
 

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