Leetcode 133 clone graph (c++)

.cpp

/*
// 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:
    Node* cloneGraph(Node* node) {
        
        if(node == NULL){
            return node;
        }
        
        queue<Node*> queue;
        queue.push(node);
        
        // 建立一個 舊 -> 新的 map 
        map<Node*, Node*> map;
        map[node] = new Node(node->val);
        
        while(!queue.empty()){
            Node* cur = queue.front();
            queue.pop();
            
            for (auto neighbor : cur->neighbors){
                
                Node* cloneNeighbor = new Node(neighbor->val);
                
                // 如果 neighbor 不在 map 中
                // 1. 新增至 map 中。
                // 2. 新增至 queue 中。
                if(!map.count(neighbor)){
                    map[neighbor] = cloneNeighbor;
                    queue.push(neighbor);
                }
                
                // 將現階段 clone 出來的新節點，加入 neighbor;
                // 切記不能放 cloneNeighbor 要放 map[neighbor]
                // 因為 clone 的 neighbor 會沒有。
                map[cur]->neighbors.push_back(map[neighbor]);
            }
        }
        
        return map[node];
    }
};