forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyolophg.js
More file actions
33 lines (25 loc) ยท 978 Bytes
/
yolophg.js
File metadata and controls
33 lines (25 loc) ยท 978 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Time Complexity: O(N + E) N = Node + E = Edge
// Space Complexity: O(N + E)
var cloneGraph = function (node) {
// to keep track of all the nodes that have already been copied
const map = new Map();
// helper to perform the deep copy
const dfs = (currentNode) => {
if (!currentNode) return null;
// if the node has already been copied, return the copied one
if (map.has(currentNode)) return map.get(currentNode);
// create a new node with the current node's value
const newNode = new Node(currentNode.val);
// store this new node in the map
map.set(currentNode, newNode);
// iterate through each neighbor of the current node
for (const neighbor of currentNode.neighbors) {
// clone the neighbors and add them to the new node's neighbors
newNode.neighbors.push(dfs(neighbor));
}
// return the newly created node
return newNode;
};
// start the deep copy from the given node
return dfs(node);
};