|
1 | 1 | /* |
2 | 2 | Given ref of a node in connected undirected graph, return deep copy |
3 | | -
|
4 | 3 | Both BFS & DFS work, map original node to its copy |
5 | | -
|
6 | 4 | Time: O(m + n) |
7 | 5 | Space: O(n) |
8 | 6 | */ |
@@ -47,37 +45,60 @@ class Node { |
47 | 45 | // unordered_map<Node*, Node*> m; |
48 | 46 | // }; |
49 | 47 |
|
| 48 | +// class Solution { |
| 49 | +// public: |
| 50 | +// Node* cloneGraph(Node* node) { |
| 51 | +// if (node == NULL) { |
| 52 | +// return NULL; |
| 53 | +// } |
| 54 | +// |
| 55 | +// Node* copy = new Node(node->val); |
| 56 | +// m[node] = copy; |
| 57 | +// |
| 58 | +// queue<Node*> q; |
| 59 | +// q.push(node); |
| 60 | +// |
| 61 | +// while (!q.empty()) { |
| 62 | +// Node* curr = q.front(); |
| 63 | +// q.pop(); |
| 64 | +// |
| 65 | +// for (int i = 0; i < curr->neighbors.size(); i++) { |
| 66 | +// Node* neighbor = curr->neighbors[i]; |
| 67 | +// |
| 68 | +// if (m.find(neighbor) == m.end()) { |
| 69 | +// m[neighbor] = new Node(neighbor->val); |
| 70 | +// q.push(neighbor); |
| 71 | +// } |
| 72 | +// |
| 73 | +// m[curr]->neighbors.push_back(m[neighbor]); |
| 74 | +// } |
| 75 | +// } |
| 76 | +// |
| 77 | +// return copy; |
| 78 | +// } |
| 79 | +// private: |
| 80 | +// unordered_map<Node*, Node*> m; |
| 81 | +// }; |
| 82 | + |
50 | 83 | classSolution { |
51 | 84 | public: |
52 | 85 | Node*cloneGraph(Node* node) { |
53 | | -if (node ==NULL) { |
54 | | -returnNULL; |
55 | | - } |
56 | | - |
57 | | - Node* copy =newNode(node->val); |
58 | | - m[node] = copy; |
59 | | - |
60 | | - queue<Node*> q; |
61 | | - q.push(node); |
62 | | - |
63 | | -while (!q.empty()) { |
64 | | - Node* curr = q.front(); |
65 | | - q.pop(); |
66 | | - |
67 | | -for (int i =0; i < curr->neighbors.size(); i++) { |
68 | | - Node* neighbor = curr->neighbors[i]; |
69 | | - |
70 | | -if (m.find(neighbor) == m.end()) { |
71 | | - m[neighbor] =newNode(neighbor->val); |
72 | | - q.push(neighbor); |
73 | | - } |
74 | | - |
75 | | - m[curr]->neighbors.push_back(m[neighbor]); |
76 | | - } |
77 | | - } |
78 | | - |
79 | | -return copy; |
| 86 | +if (node ==nullptr) |
| 87 | +returnnullptr; |
| 88 | +returndfs(node); |
80 | 89 | } |
81 | 90 | private: |
82 | 91 | unordered_map<Node*, Node*> m; |
| 92 | + |
| 93 | + Node*dfs(Node* node){ |
| 94 | +if (m.find(node) != m.end()) |
| 95 | +return m[node]; |
| 96 | + |
| 97 | + Node* n =newNode(node->val); |
| 98 | + m[node] = n; |
| 99 | +for (Node* neigh : node->neighbors){ |
| 100 | + n->neighbors.push_back(dfs(neigh)); |
| 101 | + } |
| 102 | +return n; |
| 103 | + } |
83 | 104 | }; |