At first, I wrongfully used two queues, one for old nodes, the other for new nodes. But I didn’t realize that in this way, I can’t preserve the relations between old nodes and new nodes.

Use a queue as in BFS.

Because there might be loops, use map.has(node) to check if it has been iterated.

DFS

Base case:

Node is null

Node is in map, which means it’s been cloned before. So just return map.get(node).

Return type?

Cloned nodes.

What to do in each recursion?

Create a cloned node for current node.

For each child of curr node, do DFS(child) on them to get cloned node.

Push cloned children into current node’s clone.

Question:

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

1 2 3 4

class Node { public int val; public List<Node> neighbors; }

Example:

1 2 3 4 5 6 7

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).