133. Clone Graph

解題思路

用 map 紀錄走訪過該 node 與否，並用 DFS 看過整張圖。

程式碼

class Solution {
public:
    map<Node*, Node*> oldToNew;
    Node* dfs(Node* node)
    {
        if(oldToNew.count(node))
            return oldToNew[node];

        Node* clone = new Node(node->val);
        oldToNew[node] = clone;
        for(int i=0; i<node->neighbors.size(); i++)
        {
            clone->neighbors.push_back(dfs(node->neighbors[i]));
        }
        return clone;
    }
    Node* cloneGraph(Node* node) {
        if(node == nullptr)
            return nullptr;

        return dfs(node);
    }
};