🚌非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
Node* cloneGraph(Node* node) {
if(!node)
return nullptr;
stack<pair<Node*,Node*>> stk;
vector<Node* > st(101, nullptr);
Node head(0);
stk.push({node, &head});
while(stk.size()) {
auto n = stk.top();
stk.pop();
Node* i = n.first;
Node* c = n.second;
Node* new_one = nullptr;
if(!st[i->val]) {
cout << 1 << endl;
new_one = new Node(i->val);
st[i->val] = new_one;
for(auto x: i->neighbors) {
stk.push({x, new_one});
}
} else{
new_one = st[i->val] ;
}
c->neighbors.push_back(new_one);
}
return head.neighbors[0];
}
};
|
Accepted
21/21 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 100 % of cpp submissions (11.5 MB)
🚌递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
Node* cloneGraph(Node* node) {
if(!node)
return nullptr;
vc.resize(101, nullptr);
return dfs(node);
}
Node* dfs(Node* node)
{
if(!node)
return nullptr;
if(vc[node->val])
return vc[node->val];
Node* nd = new Node(node->val);
vc[nd->val] = nd;
for(auto x: node->neighbors) {
nd->neighbors.push_back(dfs(x));
}
return nd;
}
private:
vector<Node*> vc;
};
|
Accepted
21/21 cases passed (16 ms)
Your runtime beats 67.78 % of cpp submissions
Your memory usage beats 100 % of cpp submissions (11.5 MB)
