Fork me on GitHub

Clone Graph

Posted on

Description

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
private:
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> oldToNew;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        if (oldToNew.find(node) == oldToNew.end()) {
            UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
            oldToNew[node] = newNode;
            for (auto neighbor: node->neighbors)
                newNode->neighbors.push_back(cloneGraph(neighbor));
            
        }
        return oldToNew[node];
    }
};