C++深度拷贝

Q.编写方法，传入参数为指向Node结构的指针，返回传入数据结构的完整拷贝。其中，Node数据结构含有两个指向其他Node指针。

Ans.思路：

• 需要记录一份映射关系：原结构到新结构的映射
  在深度优先遍历中，就能判断某个结点是否复制过。

typedef map<Node*, Node*> NodeMap;

Node* copy_recursive(Node* cur, Node& nodeMap) {
  if (cur == NULL) {
    return NULL;
  }

  NodeMap::iterator i = nodeMap.find(cur);
  if (i != nodeMap.end()) {
    return i->second;
  }

  Node* node = new Node;
  nodeMap[cur] = node;
  node->ptr1 = copy_recursive(cur->ptr1, nodeMap);
  node->ptr2 = copy_recursive(cur->ptr2, nodeMap);
  return node;
}

Node* copy_structure(Node* root) {
  NodeMap nodeMap;
  return copy_recursive(root, nodeMap);
}