深度遍历,由于是图。所以我们需要用一个map维持clone过的节点,以及对应的新节点。遇到的时候直接赋值,避免再次陷入clone流程中。
递归最简单。
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(node == NULL) return NULL; UndirectedGraphNode *nnode = new UndirectedGraphNode(node->label); visited[node] = nnode; for(int i = 0; i < node->neighbors.size(); i++) { UndirectedGraphNode *t = NULL; auto itr = visited.find(node->neighbors[i]); if(itr != visited.end()) t = itr->second; else t = cloneGraph(node->neighbors[i]); nnode->neighbors.push_back(t); } return nnode; } map<UndirectedGraphNode*, UndirectedGraphNode*> visited; };