9.15 BFS中等 133 Clone Graph review 138 随机链表的复制

133 Clone Graph

在这里插入图片描述

//错误代码class Solution {
public:Node* cloneGraph(Node* node) {//邻接表、BFS---》类似于二叉树的层次遍历if(!node || !node->val) return node;//构造队列queue<Node*> prev;prev.push(node);//构造新的图结点列表vector<Node*> adjList;//辅助数组// 哈希集合用于记录访问过的节点unordered_set<Node*> visited;visited.insert(node);while(prev.empty()){//获取结点并出栈Node* newNode = new Node();Node* curr = prev.front();prev.pop();newNode->val = curr->val;for(Node* neighbor : curr->neighbors){//复制对应的邻接点newNode->neighbors.push_back(neighbor);// 如果邻居没有被访问过if (visited.find(neighbor) == visited.end()) {prev.push(neighbor);         // 将未访问的邻居加入队列visited.insert(neighbor); // 标记为已访问}}adjList.push_back(newNode);}return adjList[0];}
};)

在克隆图的过程中，直接使用了原图中的邻居列表（newNode->neighbors.push_back(neighbor)），而没有克隆邻居节点的副本。实际上，需要复制整个图中的节点及其连接关系，因此应为每个节点创建新的副本，而不是直接使用原图的邻居节点。
图的克隆和链表的复制（特别是带随机指针的链表的深度复制138） 很类似。两者都涉及节点的复制，并且不仅仅是单独复制节点本身，还必须考虑其邻接点或其他关联节点（例如，图的邻居节点或链表的随机指针）。

/*
// 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) return nullptr;//原结点-->克隆结点unordered_map<Node* , Node*> cloneNodes;//BFSqueue<Node*> prev;prev.push(node);//第一个克隆结点cloneNodes[node] = new Node(node->val);while(!prev.empty()){Node* curr = prev.front();prev.pop();for(Node* neighbor : curr->neighbors){//如果邻居结点还没有被克隆if(cloneNodes.find(neighbor) == cloneNodes.end()){cloneNodes[neighbor] = new Node(neighbor->val);//加入队列prev.push(neighbor);}//将克隆的邻居节点加入当前克隆节点的邻接表cloneNodes[curr]->neighbors.push_back(cloneNodes[neighbor]);}}return cloneNodes[node];}
};

138 随机链表的复制

在这里插入图片描述

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(!head) return nullptr;//建立新链表Node* p = head;             //p是原链表指针Node* dum = new Node(0);Node* temp = dum;           //temp是新链表指针//构造哈希表unordered_map<Node* , Node*> copyList;//第一次遍历原链表，复制next指针while(p){Node* node = new Node(p->val);temp->next = node;copyList[p] = node;temp = temp->next;p = p->next;}//第二次遍历原链表，复制randomp = head;temp = dum->next;while(p){if(p->random != nullptr){temp->random = copyList[p->random];}temp = temp->next;p = p->next;}return dum->next;}
};