力扣133. 克隆图

本文主要是介绍力扣133. 克隆图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

深度优先遍历

• 思路：
  • 使用一个哈希表存储已经被克隆过的节点，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;
};

这篇关于力扣133. 克隆图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---