鏈接：
https://leetcode-cn.com/problems/clone-graph/
關(guān)鍵思路：
1.題目中明明確表示不會(huì)超過(guò)100個(gè)數(shù)據(jù)，所以用了一個(gè)數(shù)組
2.每個(gè)節(jié)點(diǎn)克隆分兩步：new一個(gè)節(jié)點(diǎn)和克隆鄰居的指針规个，兩步都結(jié)束才算完成秆吵。
3.new節(jié)點(diǎn)的時(shí)候放到task列表中奸披，克隆鄰居指針的時(shí)候要到已有信息中找一下是否有這個(gè)節(jié)點(diǎn)坟漱。
class Solution {
public:
// 新的節(jié)點(diǎn)與舊的鄰居們一一對(duì)應(yīng)
struct CloneInfo {
int success; // 是否完成克隆
Node* newNode; // 新的節(jié)點(diǎn)
};
Node* cloneGraph(Node* node)
{
if (node == nullptr) {
return nullptr;
}
vector<CloneInfo> cloneInfo(101); // 克隆信息
queue<Node*> task; // 任務(wù)表
CloneInfo head = {
0,
CreateHead(node),
};
cloneInfo[head.newNode->val] = head;
task.push(head.newNode);
// 克隆整張表
Clone(cloneInfo, task);
return head.newNode;
}
private:
Node* CreateHead(Node* node)
{
Node* head = new Node;
head->val = node->val;
// 先用舊的鄰居表
head->neighbors = node->neighbors;
return head;
}
void Clone(vector<CloneInfo> cloneInfo, queue<Node*>& task)
{
// 遍歷任務(wù)表
while (!task.empty()) {
Node* node = task.front();
// 克隆鄰居們
vector<Node*>& neighbor = node->neighbors;
auto neighborSize = neighbor.size();
for (size_t i = 0; i < neighborSize; i++) {
if (cloneInfo[neighbor[i]->val].newNode == nullptr) {
Node* node = new Node;
node->val = neighbor[i]->val;
// 先用舊的鄰居表
node->neighbors = neighbor[i]->neighbors;
CloneInfo info = {
0,
node,
};
cloneInfo[info.newNode->val] = info;
task.push(info.newNode);
}
node->neighbors[i] = cloneInfo[neighbor[i]->val].newNode;
}
cloneInfo[node->val].success = 1;
task.pop();
}
}
};
