原题链接:Leecode 133. 克隆图
官解:Leecode 133. 克隆图
DFS
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
map<Node*,Node*> m;
Node* cloneGraph(Node* node) {
if(node==NULL) return node;
if(m.find(node)!=m.end()) return m[node];
Node* root=new Node(node->val);
m[node]=root;
for(auto neighbor : node->neighbors)
{
root->neighbors.push_back(cloneGraph(neighbor));
}
return root;
}
};
BFS
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
map<Node*,Node*> m;
Node* cloneGraph(Node* node) {
if(node==NULL) return node;
queue<Node* > q;
m[node]=new Node(node->val);
q.push(node);
while(!q.empty())
{
auto tmp=q.front(); q.pop();
for(auto neighbor : tmp->neighbors)
{
if(m.find(neighbor)==m.end())
{
m[neighbor]=new Node(neighbor->val);
q.push(neighbor);
}
m[tmp]->neighbors.push_back(m[neighbor]);
}
}
return m[node];
}
};