c++ - Interview Coding - 将指向一个Node结构的指针作为参数，并返回传入数据结构的完整拷贝

Question

这是一个我觉得很有趣的面试问题。

编写一个方法，将指向 Node 结构的指针作为参数，并返回传入数据结构的完整拷贝。

Node 结构包含两个指向其他 Node 结构的指针。例如，方法签名可能如下所示:

Node* Copy(Node* root);

---

注意 - 不要对数据结构做任何假设——它可以是树、链表、图等。

对于任何数据结构如何做到这一点？

Answer 1

在通用图的情况下，您需要从原始图中的节点到新图中的节点的映射，以便在遇到循环时创建正确的链接。如果你碰巧在每个节点中都有额外的临时空间，大到足以容纳一个指针，那么你可以将映射直接存储在节点中；否则，您将需要使用外部映射，例如关联数组或哈希表。

然后就是遍历图，复制节点，查找对应的边。像这样:

struct Node
{
    Node(int _data) : data(_data) { memset(links, 0, sizeof(links)); }

    int data;
    Node *links[2];
}

Node *Copy(Node *root)
{
    typedef std::map<Node*, Node*> NodeMap;
    NodeMap nodeMap;
    std::deque<Node*> nodesToVisit;

    // Set up initial new root and mapping for the root
    Node *newRoot = new Node(root->data);
    nodeMap[root] = newRoot;

    // Breadth-first search the graph
    nodesToVisit.push_back(root);

    while(!nodesToVisit.empty())
    {
        Node *cur = nodesToVisit.front();
        nodesToVisit.pop_front();

        Node *newCur = nodeMap[cur];
        for(int i = 0; i < 2; i++)
        {
            Node *link = cur->links[i];
            if(link)
            {
                // If we've already created the corresponding node for this
                // link, use that.  Otherwise, create it and add it to the map.
                NodeMap::iterator mappedLink = nodeMap.find(link);
                if(mappedLink != nodeMap.end())
                {
                    newCur->links[i] = mappedLink->second;
                }
                else
                {
                    Node *newLink = new Node(link->data);
                    nodeMap[link] = newLink;
                    newCur->links[i] = newLink;
                    nodesToVisit.push_back(link);
                }
            }
        }
    }

    return newRoot;
}