题目
原文：
Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed-in data structure. The Node structure contains two pointers to other Node structures.
译文：
写一个函数，其中一个参数是指向Node结构的指针，返回传入数据结构的一份完全拷贝。 Node结构包含两个指针，指向另外两个Node。
解答
以下算法将维护一个从原结构的地址到新结构的地址的映射， 这种映射可以让程序发现之前已经拷贝的结点，从而不用为已有结点再拷贝一份。 由于结点中包含指向Node的指针，我们可以通过递归的方式进行结点复制。以下是代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef map<Node*, Node*> NodeMap;
Node* copy_recursive(Node *cur, NodeMap &nodeMap){
if(cur == NULL){
return NULL;
}
NodeMap::iterator i = nodeMap.find(cur);
if (i != nodeMap.end()){
// we’ve been here before, return the copy
return i->second;
}
Node *node = new Node;
nodeMap[cur] = node; // map current node before traversing links
node->ptr1 = copy_recursive(cur->ptr1, nodeMap);
node->ptr2 = copy_recursive(cur->ptr2, nodeMap);
return node;
}
Node* copy_structure(Node* root){
NodeMap nodeMap; // we will need an empty map
return copy_recursive(root, nodeMap);
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/02/14/13.8/
