深度优先遍历
- 思路：
- 使用一个哈希表存储已经被克隆过的节点，key 为原节点，value 为克隆的节点；
- 从原节点开始遍历，如果已经被克隆过，则回到其克隆节点；
- 否则，克隆该节点，并存入哈希表中；
- 然后，根据其邻居节点依次递归遍历；
/*
// 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:
Node* cloneGraph(Node* node) {
if (node == nullptr) {
return node;
}
if (visited.find(node) != visited.end()) {
return visited[node];
}
Node* cloneNode = new Node(node->val);
visited[node] = cloneNode;
for (auto& neighbor: node->neighbors) {
cloneNode->neighbors.emplace_back(cloneGraph(neighbor));
}
return cloneNode;
}
private:
std::unordered_map<Node*, Node*> visited;
};文章来源地址https://www.toymoban.com/news/detail-765664.html
文章来源：https://www.toymoban.com/news/detail-765664.html
到了这里，关于力扣133. 克隆图的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
