forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0133-clone-graph.js
68 lines (52 loc) · 1.98 KB
/
0133-clone-graph.js
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
* https://leetcode.com/problems/clone-graph/
* Time O(V + E) | Space O(N)
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function(node, seen = new Map()) {
const isBaseCase = node === null;
if (isBaseCase) return null;
if (seen.has(node)) return seen.get(node);
return dfs(node, seen); /* Time O(V + E) | Space O(N) */
}
const dfs = (node, seen) => {
const clone = new Node(node.val);
seen.set(node, clone); /* | Space O(N) */
for (const neighbor of node.neighbors) {
const cloneNeighbor = cloneGraph(neighbor, seen);/* Time O(V + E) | Space O(H) */
clone.neighbors.push(cloneNeighbor); /* | Space O(V + E) */
}
return clone;
}
/**
* https://leetcode.com/problems/clone-graph/
* Time O(V + E) | Space O(N)
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function(node, seen = new Map()) {
const isBaseCase = node === null;
if (isBaseCase) return null;
seen.set(node, new Node(node.val)); /* | Space O(N) */
bfs(new Queue([ node ]), seen); /* Time O(V + E) | Space O(N) */
return seen.get(node);
};
const bfs = (queue, seen) => {
while (!queue.isEmpty()) { /* Time O(V + E) */
for (let i = (queue.size() - 1); 0 <= i; i--) {/* Time O(W) */
const node = queue.dequeue();
cloneNeighbors(node, seen, queue); /* Space O(N) */
}
}
}
const cloneNeighbors = (node, seen, queue) => {
for (const neighbor of node.neighbors) {
if (!seen.has(neighbor)) {
seen.set(neighbor, new Node(neighbor.val));/* Space O(N) */
queue.enqueue(neighbor); /* Space O(W) */
}
const [ parentClone, neighborClone ] = [ seen.get(node), seen.get(neighbor) ];
parentClone.neighbors.push(neighborClone); /* Space O(V + E) */
}
}