133. Clone Graph.md

133. 克隆图

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

示例：

输入：
{"$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 。

 

提示：

1. 节点数介于 1 到 100 之间。
2. 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
3. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
4. 必须将给定节点的拷贝作为对克隆图的引用返回。

解法一：

//时间复杂度O(n), 空间复杂度O(n)
/*
// 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) {
        Node* head = new Node(node->val, vector<Node*>());
        unordered_map<Node*, Node*> um;
        um[node] = head;
        queue<Node*> q1;
        q1.push(node);
        while(!q1.empty()) {
            Node* temp = q1.front();
            q1.pop();
            for(Node* p : temp->neighbors) {
                if(um.count(p)) {
                    um[temp]->neighbors.push_back(um[p]);
                    continue;
                }
                Node* newNode = new Node(p->val, vector<Node*>());
                um[p] = newNode;
                um[temp]->neighbors.push_back(newNode);
                q1.push(p);
            }
        }
        return head;
    }
};

解法二：

//时间复杂度O(n), 空间复杂度O(n)
/*
// 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) {
        if(!node) return nullptr;
        if(um.count(node)) return um[node];
        Node* newNode = new Node(node->val, vector<Node*>());
        um[node] = newNode;
        for(Node* p : node->neighbors) {
            newNode->neighbors.push_back(cloneGraph(p));
        }
        return newNode;
    }
private:
    unordered_map<Node*, Node*> um;
};

解法一：

层序遍历，利用一个哈希表记录原图结点与新图结点之间的对映关系。队列q1是层序遍历的辅助容器。

解法二：

先序遍历，同样利用一个哈希表记录原图结点与新图结点之间的对映关系，然后递归地复制每一个结点。

2019/12/05 00:19