3030/** see test {@link _133_CloneGraph.SolutionDFSTest } */
3131public class SolutionDFS {
3232
33+ private Map <UndirectedGraphNode ,UndirectedGraphNode >cloneMap =new HashMap <>();
34+
3335/**
3436 * DFS version, see also {@link _133_CloneGraph.Solution BFS version }
3537 * Similar to memo version top-down dp problem. First find in memo,
3638 * if we have copied that node, return it; otherwise, construct a new node
3739 * and add neighbors to it.
3840 */
3941public UndirectedGraphNode cloneGraph (UndirectedGraphNode node ) {
40- Map <UndirectedGraphNode ,UndirectedGraphNode >cloneMap =
41- new HashMap <>();
42- return cloneGraph (node ,cloneMap );
43- }
44-
45- private UndirectedGraphNode cloneGraph (UndirectedGraphNode node ,
46- Map <UndirectedGraphNode ,UndirectedGraphNode >cloneMap ) {
4742if (cloneMap .containsKey (node )) {
4843// look up in memo first
4944return cloneMap .get (node );
@@ -55,7 +50,7 @@ private UndirectedGraphNode cloneGraph(UndirectedGraphNode node,
5550// update map here, don't wait until return statement like memo version dp
5651cloneMap .put (node ,nodeCopy );
5752for (UndirectedGraphNode neighbor :node .neighbors ) {
58- nodeCopy .neighbors .add (cloneGraph (neighbor , cloneMap ));
53+ nodeCopy .neighbors .add (cloneGraph (neighbor ));
5954 }
6055return nodeCopy ;
6156 }