Java DFS solution (recursion)


  • 2
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode root) {
      if (root == null) return null;
      
      // use a map to save cloned nodes
      Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
      
      // clone the root
      map.put(root, new UndirectedGraphNode(root.label));
      
      helper(root, map);
      
      return map.get(root);
    }
    
    void helper(UndirectedGraphNode root, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
      for (UndirectedGraphNode neighbor : root.neighbors) {
        if (!map.containsKey(neighbor)) {
          map.put(neighbor, new UndirectedGraphNode(neighbor.label));
          helper(neighbor, map);
        }
        
        map.get(root).neighbors.add(map.get(neighbor));
      }
    }

Log in to reply
 

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