Clone Graph
MediumGraphs
You are given node, a reference to one node of a connected, undirected graph. Each Node has an integer val and a list neighbors of the nodes it is connected to. Return a deep copy of the whole graph: a reference to the copy of node, where every node of the copy is a brand-new Node object with the same val, and the neighbour lists have the same structure (and the same order) as in the original. No node of the original graph may appear in the copy.
If the graph is empty, node is None; return None.
How graphs are written in the examples. Node values are 1 to n, each used once. A graph is shown as an adjacency list where entry i lists the values of the neighbours of the node with val == i + 1. The node you receive is always the node with val == 1. The expected output is the copy written the same way, so it looks identical to the input.
Example 1
- Input:
- node = [[2, 3], [1, 3, 4], [1, 2], [2]]
- Output:
- [[2, 3], [1, 3, 4], [1, 2], [2]]
- Explanation
- Nodes 1, 2 and 3 form a triangle and node 4 hangs off node 2. The copy must recreate all four nodes and every edge, and following neighbours around the triangle must stay inside the copy rather than leading back into the original.
Example 2
- Input:
- node = [[2, 3, 4], [1], [1], [1]]
- Output:
- [[2, 3, 4], [1], [1], [1]]
- Explanation
- A star: node 1 is connected to 2, 3 and 4, and each of those is connected only to node 1.
Example 3
- Input:
- node = [[2], [1]]
- Output:
- [[2], [1]]
- Explanation
- Two nodes joined by a single edge. Each copy's neighbour list contains the copy of the other node.
Constraints
- The number of nodes is in the range
[0, 100] 1 <= Node.val <= 100, and everyNode.valis unique- There are no repeated edges and no self-loops
- The graph is connected, so every node can be reached from
node