思路:
用深度优先(DFS)进行遍历用map保存新旧值的映射关系代码:
struct UndirectedGraphNode { int label; vector<UndirectedGraphNode *> neighbors; UndirectedGraphNode(int x) : label(x) {}; }; class Solution { public: map<UndirectedGraphNode*, UndirectedGraphNode*> m; UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return NULL; return dfs(node); } UndirectedGraphNode *dfs(UndirectedGraphNode *node) { map<UndirectedGraphNode *, UndirectedGraphNode *>::iterator iter = m.find(node); if (iter != m.end()) return iter->second; UndirectedGraphNode *p = new UndirectedGraphNode(node->label); m.insert(pair<UndirectedGraphNode *, UndirectedGraphNode *>(node, p)); for (int i = 0; i < node->neighbors.size(); ++i) { p->neighbors.push_back(dfs(node->neighbors[i])); } return p; } };