LeetCode算法题133：克隆图解析

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int）和其邻居的列表（list[Node]）。

示例：
LeetCode算法题133：克隆图解析

输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

对于图来说一般都是DFS或者BFS，这里就用DFS了，思路就是利用一个哈希表，键存储遍历到的点的val，值存储这个点的地址，如果遍历到的点哈希表中已经有了，说明已经复制过了，直接返回，如果没有，那么就复制当前节点并加到哈希表中，然后遍历当前节点的neighbors添加到新建节点的neighbors。

C++源代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<int, Node*> m;
        return clone(node, m);
    }
    Node* clone(Node* node, unordered_map<int, Node*>& m){
        if(!node) return node;
        if(m.count(node->val)) return m[node->val];
        Node *newNode = new Node(node->val);
        m[node->val] = newNode;
        for(int i=0;i<node->neighbors.size();i++){
            newNode->neighbors.push_back(clone(node->neighbors[i], m));
        }
        return newNode;
    }
};

python3源代码：

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        m = {}
        return self.clone(node, m)
    def clone(self, node, m):
        if node==None:
            return node
        if node.val in m.keys():
            return m[node.val]
        newNode = Node(node.val, [])
        m[node.val] = newNode
        for i in range(len(node.neighbors)):
            newNode.neighbors.append(self.clone(node.neighbors[i], m))
        return newNode

LeetCode算法题133：克隆图解析

相关推荐