分步进行
(1)首先通过DFS深度优先遍历,复制节点,使用一个map来保存原来节点A和复制节点A' 即map[A]=A'
(2)通过遍历map中的key值,找到原图中节点的所有邻居节点,将该邻居节点对应的复制节点添加到key值对应的复制节点的邻居节点即可
另外注意这个题很好通过,因为这个题似乎只有一个很简单的测试用例,我看到有些人的写法是错误的这题也通过了,而且直接还回node节点居然也可以过,所以想练手的同学们可以做leetcode上的原题:leetcode133 Clone Graph 链接:https://leetcode-cn.com/problems/clone-graph/
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp; void dfs(UndirectedGraphNode* node) { if (node == nullptr) { return; } if (mp.count(node)) { return; } UndirectedGraphNode *copyNode = new UndirectedGraphNode(node->label); mp[node] = copyNode; for (auto n : node->neighbors) { dfs(n); } } UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { UndirectedGraphNode* oldNode = node; dfs(node); for (auto n : mp) { UndirectedGraphNode *first = n.first; for (int i = 0; i < first->neighbors.size(); i++) { n.second->neighbors.push_back(mp[first->neighbors[i]]); } } return mp[oldNode]; }