Java DFS solution (iterative)


  • 7
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode root) {
      if (root == null) return null;
      
      // use a stack to help DFS
      Stack<UndirectedGraphNode> stack = new Stack<UndirectedGraphNode>();
      stack.push(root);
      
      // 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));
      
      while (!stack.isEmpty()) {
        UndirectedGraphNode node = stack.pop();
        
        // handle the neighbors
        for (UndirectedGraphNode neighbor : node.neighbors) {
          if (!map.containsKey(neighbor)) {
            // clone the neighbor
            map.put(neighbor, new UndirectedGraphNode(neighbor.label));
            // add it to the next level
            stack.push(neighbor);
          }
          
          // copy the neighbor
          map.get(node).neighbors.add(map.get(neighbor));
        }
      }
      
      return map.get(root);
    }

Log in to reply
 

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