Graphs Traversing a graph
448. Clone Graph
You are given node, one node of a connected undirected graph. Each node holds a value val and a list
neighbors of the nodes it shares an edge with.
Return a deep copy of the graph: a new node for every node, with the same value, and the same edges between the new nodes. Each new node lists the copies of its old node's neighbours, in the same order. No node of the copy may be a node of the given graph, and the given graph must be as it was when your function returns.
The examples write a graph as its adjacency list, adjList. The nodes are numbered from 1, and each node's
value is its number. The first row lists the neighbours of node 1, the second row those of node 2, and so
on. node is node 1. So adjList = [[2],[1,3],[2]] is three nodes in a line, 1 – 2 – 3, and node is
the node with value 1. [] is an empty graph: node is null, and you return null.
The output shows the copy you return the same way, read from the node you return. If the copy is not a deep
copy, the output says what is wrong, such as the copy shares a node with the original.
Example 1
Input: adjList = [[2, 3], [1, 3, 4], [1, 2], [2]]
[[2,3],[1,3,4],[1,2],[2]]Explanation: Nodes 1, 2 and 3 are all joined to each other, and node 4 is joined only to node 2. The copy has four new nodes joined the same way, and we return the new node with value 1.
Example 2
Input: adjList = [[2, 3, 4, 5], [1], [1], [1], [1]]
[[2,3,4,5],[1],[1],[1],[1]]Explanation: Node 1 is joined to every other node, and no other pair is joined. The new node 1 lists the four other new nodes, in the order 2, 3, 4, 5.
Example 3
Input: adjList = []
[]Explanation: The graph is empty, so node is null and the answer is null.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 1050 ≤ number of edges ≤ 2 × 105- Node i has the value i, for every i from 1 to the number of nodes.
- Every edge works both ways: if node a lists node b, then node b lists node a.
- No edge appears twice, and no node is joined to itself.
- The graph is connected: every node can be reached from node 1.
Clarifying questions
What you would ask an interviewer before writing any code.