Leetcode 133 Clone Graph

解题报告

题目的要求是clone一个无向图。
这个无向图的表达方式类似于adjacency list，但是不一样的地方在于，不会重复出现edges。
比如0，1，2
0: 1,2
对于1来说
1:2
它的neighbor list中就没有0。所以每个edge只会出现一次。

要求是clone这个graph。那么问题来了
1 How to clone a node?

1. clone value of this node
2. clone node's neighbors list
   1> clone one neighbor
   2> add this cloned one to the neighbors list

2 Where should I store the cloned graph? Do I need a dummy node point to the starting node?
Overthinking.
Just think for a single node, if u clone it, return the cloned one. That's what we need.

3 What is minimum subquestion?
Simply to say, for a single node, just copy this node.
Clone details are listed on the question 1.

Then we start to analyze this problem using the pattern:
Input:
node

during the process analysis, we know we should also have another input:
HashMap<Integer, Node>

Output:
clonedNode

Process:
****************Base case**************
what is the base cases?
node == null
what should return? null

self-cycle situation
How to find self-cycle?
cache some things using HashSet? or HashMap? since the label is unique.
what to return?
return self which is already cloned.
So we should use HashMap<Integer, Node>

****************Process**************
Clone curNode, copy its value to clonedNode
Clone its neighbors (recursion call)
add the cloned neighbors to the cloneNode's neighbors list

return clonedNode

public class Solution {
    private HashMap<Integer, UndirectedGraphNode> map;
    private UndirectedGraphNode dfsClone(UndirectedGraphNode curNode, HashMap<Integer, UndirectedGraphNode> map) {
        // base case
        if (curNode == null) {
            return null;
        }
        
        if (map.containsKey(curNode.label)) {  //  self cycle
            return map.get(curNode.label);
        }
        
        // process
        UndirectedGraphNode cloneNode = new UndirectedGraphNode(curNode.label);
        map.put(cloneNode.label, cloneNode);
        
        for (UndirectedGraphNode node : curNode.neighbors) {
            cloneNode.neighbors.add(dfsClone(node, map));
        }
        
        return cloneNode;
    }
    
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        map = new HashMap<>();
        return dfsClone(node, map);
    }
}