Cracking the coding interview--Q13.8

February 14, 2013
作者:Hawstein
出处:http://hawstein.com/posts/13.8.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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的指针,我们可以通过递归的方式进行结点复制。以下是代码:

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