首先,这是个图的问题,二话不说,咱先搬出BFS和DFS两大法宝。
基本思路是:创建一个unordered_map
,其中保存指向旧节点的指针到指向新节点的指针的映射,同时也用它来判断旧节点是否被遍历过。
BFS代码如下:
// // Created by jt on 2020/9/23. // #include <vector> #include <unordered_map> #include <queue> using namespace std; class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return nullptr; unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp; queue<UndirectedGraphNode*> qu; qu.push(node); // BFS while (!qu.empty()) { UndirectedGraphNode* oldNode = qu.front(); qu.pop(); UndirectedGraphNode* newNode = mp.count(oldNode) != 0 ? mp[oldNode] : new UndirectedGraphNode(oldNode->label); mp[oldNode] = newNode; for (auto p : oldNode->neighbors) { UndirectedGraphNode* q; if (mp.count(p) != 0) { q = mp[p]; } else { q = new UndirectedGraphNode(p->label); mp[p] = q; // 如果旧节点没有遍历过,加入队列 qu.push(p); } newNode->neighbors.push_back(q); } } return mp[node]; } };
DFS代码如下:
// // Created by jt on 2020/9/23. // #include <vector> #include <unordered_map> using namespace std; class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return nullptr; unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp; return dfs(node, mp); } UndirectedGraphNode* dfs(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &mp) { if (!node) return nullptr; if (mp.count(node) != 0) return mp[node]; UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label); mp[node] = newNode; for (auto p : node->neighbors) { newNode->neighbors.push_back(dfs(p, mp)); } return newNode; } };