133.Clone Graph

這題主要麻煩在於, 如果已經複製過的鄰居, 再次被遇到怎麼辦,

查到一種方法, 可以用hashtable去紀錄 正體跟複製體的map, 一旦發現複製體已經在就可以直接取得, 非常聰明

dfs:

class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<Node *, Node *> m;
        return dfs(node, m);
    }
    Node* dfs(Node* root, unordered_map<Node*, Node*> &m){
        if(!root){
            return nullptr;
        }
        if(m.count(root)){
            return m[root];
        }
        Node *clone = new Node(root->val);
        m[root] = clone;
        for(Node *neighbor: root->neighbors){
            clone->neighbors.push_back(dfs(neighbor, m));
        }
        return clone;
    }
};

Bfs:

class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<Node *, Node *> m;
        queue<Node *> q;
        m[node] = new Node(node->val);
        q.push(node);
        while(!q.empty()){
            int len = q.size();
            Node *cur = q.front();
            q.pop();
            Node *clone;
            if(!m.count(cur)){
                clone = new Node(cur->val);
            }else{
                clone = m[cur];
            }
            for(auto n: cur->neighbors){
                if(!m.count(n)){
                    m[n] = new Node(n->val);
                    q.push(n);
                }
                clone->neighbors.push_back(m[n]);
            }
        }
return m[node];
    }
};