JAVA-----------Easy Version To Understand!!!!!


  • 0
    H

    =## Key to Solve This Problem
    1.A queue is used to do breath first traversal.
    2.a map is used to store the visited nodes. It is the map between original node and copied node. ##

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    	if (node == null)
    		return null;
    	HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();//
    	Queue<UndirectedGraphNode> queue = new LinkedList<>();
    	UndirectedGraphNode firstNode = new UndirectedGraphNode(node.label);
    	map.put(node, firstNode);
    	queue.offer(node);
    	while (!queue.isEmpty()) {
    		UndirectedGraphNode beforeCloneNode = queue.poll();
    		for (int i = 0; i < beforeCloneNode.neighbors.size(); i++) {
    			UndirectedGraphNode nearNode = beforeCloneNode.neighbors.get(i);
    			if (map.get(nearNode) != null) {
    				map.get(beforeCloneNode).neighbors.add(map.get(nearNode));
    			} else {
    				UndirectedGraphNode afterCloneNode = new UndirectedGraphNode(nearNode.label);
    				map.get(beforeCloneNode).neighbors.add(afterCloneNode);//
    				map.put(nearNode, afterCloneNode);
    				queue.offer(nearNode);
    			}
    		}
    	}
    	return firstNode;
    }

Log in to reply
 

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