Leetcode133.克隆图

 　　需要注意图中存在环路。

　　JAVA：

    public final Node cloneGraph(Node node) {
        return deepCopy(node, new HashMap<Integer, Node>());
    }

    private Node deepCopy(Node node, HashMap<Integer, Node> hisMap) {
        if (null == node) return node;
        if (hisMap.keySet().contains(node.val)) return hisMap.get(node.val);
        Node targetNode = new Node(node.val);
        hisMap.put(node.val, targetNode);
        targetNode.neighbors = new ArrayList<Node>(node.neighbors.size());
        for (int i = 0; i < node.neighbors.size(); i++) {
            targetNode.neighbors.add(deepCopy(node.neighbors.get(i), hisMap));
        }
        return targetNode;
    }

　　JS:

var cloneGraph = function (node) {
    return deepCopy(node, {});
};

var deepCopy = function (node, hisMap) {
    if (!node) return node;
    if (hisMap[node.val]) return hisMap[node.val];
    let targetNode = new Node(node.val, []);
    hisMap[node.val] = targetNode;
    for (let i = 0; i < node.neighbors.length; i++) {
        targetNode.neighbors.push(deepCopy(node.neighbors[i], hisMap));
    }
    return targetNode;
}

　　C:

struct Node *deepCopy(struct Node *graph, struct Node **graphArray)
{
    if (NULL == graph || NULL == graph->val)
        return graph;
    if (NULL != graphArray[graph->val])
        return graphArray[graph->val];
    struct Node *targetNode = (struct Node *)malloc(sizeof(struct Node));
    targetNode->val = graph->val;
    targetNode->numNeighbors = graph->numNeighbors;
    targetNode->neighbors = malloc(sizeof(struct Node *) * graph->numNeighbors);
    memset(targetNode->neighbors, 0, sizeof(struct Node *) * graph->numNeighbors);
    graphArray[graph->val] = targetNode;
    for (int i = 0; i < graph->numNeighbors; i++)
    {
        targetNode->neighbors[i] = deepCopy(graph->neighbors[i], graphArray);
    }
    return targetNode;
}

struct Node *cloneGraph(struct Node *s)
{
    struct Node **graphArray = (struct Node **)malloc(sizeof(struct Node *) * 101);
    memset(graphArray, 0, sizeof(struct Node *) * 101);
    struct Node *targetRoot = deepCopy(s, graphArray);
    free(graphArray);
    return targetRoot;
}

　　Python:

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        return self.deepCopy(node, {})

    def deepCopy(self, node: Optional['Node'], visited) -> Optional['Node']:
        if not node:
            return node
        if node in visited:
            return visited[node]
        neighbors = node.neighbors;
        copyNode = Node(node.val, [])
        visited[node] = copyNode
        for neighbor in neighbors:
            cpoyNeighbor = self.deepCopy(neighbor, visited)
            copyNode.neighbors.append(cpoyNeighbor)
        return copyNode