- a DFS *or* BFS traversal would appropriately create a deep copy of the graph
🤔What Did I Struggle With?
~
💡 Explanation of Solution
- Base Case:
- If the input node is `nullptr`, return `nullptr`.
- Visited Map:
- Use a map (or hash table) to store the original node as the key and the cloned node as the value. This helps ensure that each node is only cloned once and avoids infinite loops in cyclic graphs.
- Create a Clone:
- If the current node has not been visited, create a new node with the same value as the current node. Store this clone in the map.
- Recurse on Neighbors:
- For each neighbor of the current node, recursively call the `cloneGraph` function to get their cloned version, and add these to the clone's neighbors.
- Return the Clone:
- After all neighbors have been processed, return the clone of the current node.
⌛ Complexity Analysis
Time Complexity: O(n) since we are traversing each node in the graph exactly once, with help from the visited map
Space Complexity: O(n) , the deep copy of the graph has n nodes, but we are also utilising n additional auxilary space to track visited nodes as we traverse
💻 Implementation of Solution
class Solution {public: // stores the original node and cloned node unordered_map<Node*, Node*> visited; Node* cloneGraph(Node* node) { // Base case: if the input node is nullptr, return nullptr if (!node) return nullptr; // If the node has already been cloned, return its clone if (visited.find(node) != visited.end()) { return visited[node]; } // Create a new node with the value of the current node Node* clone = new Node(node->val); visited[node] = clone; // Mark the node as cloned // Recursively clone all neighbors for (Node* neighbor : node->neighbors) { clone->neighbors.push_back(cloneGraph(neighbor)); } return clone; }};