这是一个我觉得很有趣的面试问题。
编写一个方法，将指向Node结构的指针作为参数，并返回传入数据结构的完整副本。
Node结构包含两个指向其他Node结构的指针。 例如，方法签名可能如下所示：
Node* Copy(Node* root);
注意 - 不要对数据结构做任何假设 - 它可以是树，链表，图表等。
如何为任何数据结构做到这一点？
这是一个我觉得很有趣的面试问题。
编写一个方法，将指向Node结构的指针作为参数，并返回传入数据结构的完整副本。
Node结构包含两个指向其他Node结构的指针。 例如，方法签名可能如下所示：
Node* Copy(Node* root);
注意 - 不要对数据结构做任何假设 - 它可以是树，链表，图表等。
如何为任何数据结构做到这一点？
在通用图形的情况下，您需要从原始图形中的节点到新图形中的节点的映射，以便在遇到循环时，创建正确的链接。如果您在每个节点中碰巧有额外的临时空间，大到足以容纳指针，那么您可以将映射直接存储在节点中;否则，您将需要使用外部映射，例如关联数组或散列表。
然后，只需遍历图形，复制节点，查找相应的边缘即可。像这样的东西：
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;
}
所述问题是不可能的。您必须假设整个数据结构完全存储在可从该初始节点访问的节点内容中。但这不是你被允许做出的假设。即使您的标准基本双链表也可能不符合该描述。
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;
}
}
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's 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，如果left或right为NULL则不会失败。
[编辑]亚当罗森菲尔德让我意识到，如果网络中存在循环，这是不正确的。不得不从头开始重写。由于需要大量代码，我更喜欢他的代码for循环。
return new Node(*node);
特技提问？
你应该递归地写它;
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;
}
因此，这不会对数据类型做出任何假设
鉴于存在复制构造函数，它只复制节点的内容而不复制其子节点：
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);
}