Given a node in a graph node
, clone the graph, and return the cloned node.
When you modify the cloned graph, it should have no effect on the original graph. This means that you can't simply return the original node as the solution to the problem.
0. Problem
We want to write a function that takes in a node
, and returns its clone.
1. Recursion
To write the recursion, we first have to copy the current node. After we do this, we need to point the node to the clones of its neighbor nodes, like this:
Here's the recursion:
2. Base case
We need to make sure we don't enter any infinite cycles since we're dealing with graphs. We should stop if we get to a node we've already cloned. This way we never clone the same node twice, so our code can't possibly run forever.
To do this, we'll store all the nodes we've visited in a HashMap called cloneOfNode
. Here's the base case:
3. Code
Here's the full code:
Time Complexity O(n). We visit every node in the graph.
Space Complexity O(n). We store every node in the HashMap cloneOfNode
.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()