👽递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
Node* flatten(Node* head) {
helper(head);
return head;
}
Node* helper(Node* node) {
if(!node || (!node->child && !node->next))
return node;
auto nex = node->next;
auto chil = helper(node->child);
if(chil) {
node->next = node->child;
node->child->prev = node;
chil->next = nex;
if(nex) nex->prev = chil;
node->child = nullptr;
}
return nex ? helper(nex) : chil;
}
};
|
Accepted
22/22 cases passed (8 ms)
Your runtime beats 73.19 % of cpp submissions
Your memory usage beats 55.69 % of cpp submissions (10 MB)
🤡DFS
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
31
| class Solution {
public:
Node* flatten(Node* head) {
if(!head)
return head;
stack<Node*> stk;
stk.push(head);
Node* pre = nullptr;
while(stk.size()) {
auto nd = stk.top();
stk.pop();
if(nd->next) {
stk.push(nd->next);
}
if(nd->child) {
stk.push(nd->child);
nd->child = nullptr;
}
if(pre) {
pre->next = nd;
nd->prev = pre;
}
pre = nd;
}
return head;
}
};
|
Accepted
22/22 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 60.78 % of cpp submissions (9.7 MB)
