https://leetcode.com/problems/clone-graph/

对于这种自己构建数据结构的题一直拿不准。
拿不准dfs和bfs分别应该在什么时候new。
比如树的序列化。
比如clone graph。

Clone Graph
dfs:

class Solution {
    unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> mp;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return NULL;
        if(mp.find(node) == mp.end()) {
            UndirectedGraphNode * newnode = new UndirectedGraphNode(node->label);
            mp[node] = newnode;
            for(int i = 0; i < node->neighbors.size(); i++) {
                newnode->neighbors.push_back(cloneGraph(node->neighbors[i]));
            }
        }
        return mp[node];
    }
};   

bfs:

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return NULL;
        unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> mp;
        queue<UndirectedGraphNode *> q;
        q.push(node);
        UndirectedGraphNode * newn = new UndirectedGraphNode(node->label);
        mp[node] = newn;
        while(!q.empty()) {
            UndirectedGraphNode * n = q.front();
            q.pop();
            for(int i = 0; i < n->neighbors.size(); i++) {
                UndirectedGraphNode * nei = n->neighbors[i];
                if(mp.find(nei) == mp.end()) {
                    q.push(nei);
                    newn = new UndirectedGraphNode(nei->label);
                    mp[nei] = newn;
                }
                mp[n]->neighbors.push_back(mp[nei]);
            }
        }
        return mp[node];
    }
};