LeetCode 133克隆图报错：需返回所有节点副本，如何修正？

我在做LeetCode第133题「克隆图」时，运行下面的C++代码后一直收到错误提示：

You must return a copy of all the nodes in the original graph

原代码 #

/*
// 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 {
private:
    void BreadthFirstSearch (struct Node* node) {

        bool check[128] = { 0, };

        queue<struct Node*> buffer;
        buffer.push (node);

        while (!buffer.empty()) {

            auto current = buffer.front(); buffer.pop();

            if (check[current->val] == true) continue;
            else check[current->val] = true;

            cout << current->val << " : ";

            for (const auto& element : current->neighbors) {

                buffer.push (element);
                cout << element->val << " ";
            }
            cout << endl;
        }
        return;
    }

public:
    struct Node* cloneGraph(struct Node* node) {

        if (node == NULL) return NULL;

        bool check[128] = { 0, };

        queue<struct Node*> buffer, copyBuffer;
        buffer.push (node);

        struct Node* clone = new struct Node;
        if (clone == NULL) throw;

        clone->val = node->val;
        copyBuffer.push (clone);

        while (!buffer.empty()) {

            auto& current = buffer.front(); buffer.pop();
            auto& destination = copyBuffer.front(); copyBuffer.pop();

            if (check[current->val] == true) continue;
            else check[current->val] = true;

            // cout << current->val << ' ' << destination->val << ' ';
            // printf ("%p %p
", &current, &destination);

            for (const auto& element : current->neighbors) {

                buffer.push (element);

                struct Node* newNode = new struct Node;
                if (newNode == NULL) throw;

                newNode->val = element->val;
                destination->neighbors.push_back (newNode);

                copyBuffer.push (newNode);
            }
        }

        BreadthFirstSearch (node); cout << endl;
        BreadthFirstSearch (clone); cout << endl;

        return clone;
    }
};

错误原因分析 #

• 重复创建节点，未复用已克隆对象：遍历原节点邻居时，每次都新建Node，导致同一个原节点被多次克隆（比如节点2被多个节点指向时，会生成多个val为2的克隆节点），最终克隆图节点数量远超原图，不符合题目要求。
• 缺少原节点与克隆节点的映射：没有用哈希表记录已克隆的节点，无法在后续遇到相同原节点时复用对应的克隆节点，导致邻居指向错误。
• BFS处理逻辑缺陷：check数组仅标记原节点是否被处理，但处理邻居时未判断该邻居是否已被克隆，直接新建节点，破坏了克隆图的结构一致性。

修正后的代码 #

/*
// 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;
    }
};
*/

#include <unordered_map>
using namespace std;

class Solution {
private:
    void BreadthFirstSearch(Node* node) {
        bool check[128] = {0};
        queue<Node*> buffer;
        buffer.push(node);

        while (!buffer.empty()) {
            auto current = buffer.front();
            buffer.pop();

            if (check[current->val]) continue;
            check[current->val] = true;

            cout << current->val << " : ";
            for (const auto& element : current->neighbors) {
                buffer.push(element);
                cout << element->val << " ";
            }
            cout << endl;
        }
    }

public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;

        // 原节点到克隆节点的映射表，避免重复创建
        unordered_map<Node*, Node*> nodeMap;
        queue<Node*> buffer;

        // 创建根节点的克隆，并加入映射和队列
        Node* cloneRoot = new Node(node->val);
        nodeMap[node] = cloneRoot;
        buffer.push(node);

        while (!buffer.empty()) {
            auto current = buffer.front();
            buffer.pop();

            // 遍历当前原节点的所有邻居
            for (auto neighbor : current->neighbors) {
                // 如果邻居还没被克隆，创建新节点并加入映射和队列
                if (nodeMap.find(neighbor) == nodeMap.end()) {
                    nodeMap[neighbor] = new Node(neighbor->val);
                    buffer.push(neighbor);
                }
                // 将克隆节点的邻居指向对应的克隆对象
                nodeMap[current]->neighbors.push_back(nodeMap[neighbor]);
            }
        }

        // BreadthFirstSearch(node); cout << endl;
        // BreadthFirstSearch(cloneRoot); cout << endl;

        return cloneRoot;
    }
};

修正说明 #

1. 新增unordered_map<Node*, Node*>来存储原节点到克隆节点的映射，确保每个原节点只被克隆一次。
2. 处理邻居时，先检查映射表：如果邻居未被克隆则创建并加入映射，否则直接复用已有的克隆节点。
3. 简化BFS逻辑，确保克隆图的邻居关系与原图完全一致，不会出现重复节点。

内容的提问来源于stack exchange，提问作者Michael Johnson