Кодирование интервью. Возьмите указатель на структуру Node в качестве параметра и верните полную копию переданной структуры данных

Ответ 1

В случае с общим графиком вам нужно сопоставить узлы в исходном графе с узлами нового графика, так что, когда встречается цикл, создается правильная ссылка. Если у вас есть дополнительное временное пространство в каждом node, достаточно большом, чтобы удерживать указатель, вы можете сохранить отображение непосредственно в узлах; в противном случае вам потребуется использовать внешнюю карту, такую ​​как ассоциативный массив или хеш-таблицу.

Затем это просто вопрос обхода графика, копирования узлов и поиска соответствующих ребер. Что-то вроде этого:

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

Ответ 2

Задача, изложенная, невозможна. Вы должны предположить, что вся структура данных хранится полностью внутри содержимого узлов, которые доступны из этого исходного. Но это не предположение, которое вам разрешено делать. Даже ваш стандартный базовый двойной связанный список может не соответствовать этому описанию.

Ответ 3

class Copier {
  std::map <Node*, Node*> copies;

  Node* Copy(Node* n) {
    if (!n) return 0;
    Node*& copy = copies[n];
    if (!copy) {
      copy = new Node();
      copy.node1 = Copy(n.node1);
      copy.node2 = Copy(n.node2);
    }
    return copy;
  }
}

Ответ 4

Node* Copy(Node* root) {
   if (root == NULL)
       return root;
   std::unordered_map<Node*, Node*> completed; 
   std::deque<Node*> todo;
   Node *ret = new Node(*scur);
   completed.push_back(std::make_pair(root, ret));
   todo.push_pack(root); 

   //while there more nodes to duplicate
   do { 
       //duplicate the node
       Node* oldNode = todo.back();
       Node* newNode = completed[cur];
       todo.pop_back();

       if(oldNode->left) {
           auto iter = completed.find(oldNode->left);
           //if it has a left child that needs duplicating, add it to the todo list
           if (iter == completed.end()) {
               newNode->left = new Node(*(oldNode->left));
               completed.push_back(std::make_pair(oldNode->left, newNode->left));
               todo.push_back(oldNode->left);
           } else {
               newNode->left = completed[oldNode->left];
           }
       }
       if(oldNode->right) {
           auto iter = completed.find(oldNode->right);
           //if it has a right child that needs duplicating, add it to the todo list
           if (iter == completed.end()) {
               newNode->right = new Node(*(oldNode->right));
               completed.push_back(std::make_pair(oldNode->right, newNode->right));
               todo.push_back(oldNode->right);
           } else {
               newNode->right= completed[oldNode->right];
           }
       }

   } while(todo.empty() == false)
   //return the translation of the root
   return ret;
}

Не имеет, root может быть NULL, не терпит неудачу, если слева или справа NULL.

[Edit] Адам Розенфилд заставил меня понять, что это было неправильно, если в сети были петли. Пришлось переписывать почти с нуля. Из-за большого количества требуемого кода я предпочитаю его код для цикла.

Ответ 5

return new Node(*node);

Вопрос об уловке?

Ответ 6

Вы должны записать его рекурсивно;

Node * Copy( Node * root )
{
    Node * node_copy;

    node_copy = new Node; // Assume Node1 and Node2 are initialized to 0
    node_copy->content = root->content;

    if( root->Node1 ) node_copy->Node1 = Copy( root->Node1 );
    if( root->Node2 ) node_copy->Node2 = Copy( root->Node2 );

    return node_copy;
}

Таким образом, это не делает никаких предположений о типе данных

Ответ 7

Учитывая, что существует конструктор копирования, который копирует только содержимое node, а не его дочерние элементы:

Node* Copy(Node* root)
{
    Node* copy = new Node(*root);
    copy->left = Copy(root->left);
    copy->right = Copy(root->right);
    return copy;
}

В более общем смысле я бы использовал копии-конструкторы, которые полностью копируют всю структуру данных:

Node* Copy(Node* root)
{
    return new Node(*root);
}