1、题目描述

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

Input:
{"id" :"1","neighbors":[{"id":"2","neighbors":[{"ref":"1"},{"id":"3","neighbors":[{"ref":"2"},{"id":"4","neighbors":[{"ref":"3"}，{"ref":"1"}],"val":4}],"val":3}],"val":2},{"ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

1. The number of nodes will be between 1 and 100.
2. The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
4. You must return the copy of the given node as a reference to the cloned graph.

2、问题描述：

• 深拷贝一个树。

3、问题关键：

• 先将每个点复制一遍，维护hash表，建立原点和新点之间的关系。
• 遍历所有的边（a，b），在新的点之间，建立新的边（a‘，b’）。

4、C++代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {}
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    unordered_map<Node*, Node*> hash;//建立一个hash表。
    Node* cloneGraph(Node* node) {
        if (!node) return node;//如果是空树，那么直接返回。
        auto p = new Node(node->val);// 将结点复制。
        hash[node] = p;//--------这是建立原点和新点之间的关系。通过原点可以找到新的点。
        dfs(node);
        return p;
    }
    void dfs(Node* node) {
        for (auto ver : node->neighbors) {//遍历node的所有的邻居结点。
            if (!hash.count(ver)) {//如果邻居结点还没有被创建一个新的点。那么创建一个，而且说明没有被遍历过，那么也dfs一遍。
                hash[ver] = new Node(ver->val);
                dfs(ver);
            }
            hash[node]->neighbors.push_back(hash[ver]);//如果遍历过了，那么将建立和邻居的关系，变成邻居。
        }
    }
};