为什么我在 LeetCode 上尝试解决第 133 题时会出现此错误？

Question

/*
// 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\n", &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;
    }
};

我正在尝试解决LeetCode 上的第 133 号问题。我不断得到：

您必须返回原始图中所有节点的副本

需要纠正什么？

Answer 1

可以有多个边终止于同一节点，因此当一个节点已经被访问过时，您不应该像这里那样跳过迭代：

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

您可以存储指向所有复制节点的指针数组，并重用同一节点（如果已复制该节点）以维护正确的引用。

Node* copies[101]{}; // replace the check array with this
// ...
copyBuffer.push(copies[node->val] = clone);

// inside BFS:
for (const auto& element : current->neighbors) {
    if (copies[element->val]) {
        destination->neighbors.push_back(copies[element->val]);
        continue;
    }
    buffer.push(element);
    struct Node* newNode = new struct Node;
    newNode->val = element->val;
    destination->neighbors.push_back (newNode);
    copyBuffer.push(copies[element->val] = newNode);
}

此外，您不应该引用队列前面的元素，因为它们会在之后立即被删除。

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

Answer 2

• 您可以简单地使用一个

  queue

  ，而不是使用第二个

  unordered_map

  。
• 此外，您必须只按照该平台上的说明返回输出。

BFS

#include <vector>
#include <queue>
#include <unordered_map>

// // Definition for a Node.
// class Node {
// public:
//     int val;
//     std::vector<Node*> neighbors;
//     Node() {
//         val = 0;
//         neighbors = std::vector<Node*>();
//     }
//     Node(int _val) {
//         val = _val;
//         neighbors = std::vector<Node*>();
//     }
//     Node(int _val, std::vector<Node*> _neighbors) {
//         val = _val;
//         neighbors = _neighbors;
//     }
// };

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

        std::unordered_map<Node *, Node *> nodes;
        std::queue<Node *> buffer;
        buffer.push(node);

        Node *clone = new Node(node->val);
        nodes[node] = clone;

        while (!buffer.empty())
        {
            Node *current = buffer.front();
            buffer.pop();
            for (const auto &element : current->neighbors)
            {
                if (nodes.find(element) == nodes.end())
                {
                    Node *newNode = new Node(element->val);
                    nodes[element] = newNode;
                    buffer.push(element);
                }
                nodes[current]->neighbors.emplace_back(nodes[element]);
            }
        }

        return clone;
    }
};

DFS

• 您还可以考虑使用深度优先搜索方法来解决此问题，因为它更容易实现：

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <unordered_map>

struct Solution {
    Node* cloneGraph(
        Node* node
    ) {
        if (!node) {
            return nullptr;
        }

        if (nodes.find(node) == std::end(nodes)) {
            nodes[node] = new Node(node->val, {});
            for (Node* neighbor : node->neighbors) {
                nodes[node]->neighbors.emplace_back(cloneGraph(neighbor));
            }
        }

        return nodes[node];
    }

private:
    std::unordered_map<Node*, Node*> nodes;
};