思路：
一般這種遍歷都可以通過BFS或者DFS完成侨颈，我們首先通過BFS，但是需要記住哪些節(jié)點已經(jīng)拷貝過了芯义，類似于visited哈垢，我們可以用
map<Node, Node> m 的一個map來記住哪些已經(jīng)拷貝了。
具體的代碼如下：
/*
// 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;
Node* copy = new Node(node->val, {});
m[node] = copy;
stack<Node*> s;
s.push(node);
while (!s.empty()) {
Node* tmp = s.top();
s.pop();
for (auto neighbor : tmp->neighbors) {
if (m.find(neighbor) == m.end()) {
s.push(neighbor);
m[neighbor] = new Node(neighbor->val, {});
}
m[tmp]->neighbors.push_back(m[neighbor]);
}
}
return copy;
}
private:
map<Node*, Node*> m;
};
DFS:
class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node) {
return NULL;
}
if (copies.find(node) == copies.end()) {
copies[node] = new Node(node -> val, {});
for (Node* neighbor : node -> neighbors) {
copies[node] -> neighbors.push_back(cloneGraph(neighbor));
}
}
return copies[node];
}
private:
unordered_map<Node*, Node*> copies;
};
