采访编码 - 将指向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;
}