|
| 1 | +letdfs=(node:Node,memo:Map<Node,Node>)=>{ |
| 2 | +if(node===null)returnnull; |
| 3 | + |
| 4 | +//if this node has already been visited, simply return the counterpart node of the new graph and return |
| 5 | +if(memo.has(node))returnmemo.get(node); |
| 6 | + |
| 7 | +//node hasn't been already visited, create its counterpart version for the new graph |
| 8 | +letnewNode=newNode(node.val); |
| 9 | +//maps to the old graph counterpart(also marked as visited) |
| 10 | +memo.set(node,newNode); |
| 11 | + |
| 12 | +//for each edge of the old node, add that edge in the new graph node |
| 13 | +for(leti=0;i<node.neighbors.length;i++){ |
| 14 | +newNode.neighbors.push(dfs(node.neighbors[i],memo)); |
| 15 | +} |
| 16 | + |
| 17 | +returnnewNode; |
| 18 | +}; |
| 19 | + |
| 20 | +functioncloneGraph(node:Node|null):Node|null{ |
| 21 | +//uses a map, maps old graph nodes with new graph ones |
| 22 | +//it also tells us which node of the old graph have already been visited |
| 23 | +letmemo=newMap<Node,Node>(); |
| 24 | + |
| 25 | +returndfs(node,memo); |
| 26 | +} |