日野弥生：勉強しよう
LeetCode 430 - 扁平化多级双向链表
发表于2025年01月30日
深度优先搜索，dfs过程需要先处理child分支，后处理next分支。函数返回前处理prev节点。 很容易想到dfs过程需要以prev、curr、next节点作为输入参数。
但是，发现在扁平化过程中，next指针会发生改变，所以需要记录原next指针，即originNext。
注意，处理完child分支后，需要将分支置空；同时，由于深度优先搜索时，走到最后（即next指针和child指针均为空）的结点，需要记录当前位置，所以需要visit指针，便于在回溯时把最后位置的节点和回溯过程中的next节点继续连接。而，visit节点用过后就要被置为空，在递归过程中会因深度的不同的不断被改变，所以这个指针应该传引用。
由于visit指针会在遍历到不同深度的最后一个结点时赋值，所以visit指针在被传递时需要置空。
class Solution {
public:
/* visit指针会被修改 */
void dfs(Node *prev, Node *curr, Node *next, Node * &visit){
if(prev)
prev->next = curr;
/* 记录原本的next指针 */
Node *originNext = curr->next;
/* 处理完子分支后置空 */
if(curr->child)
dfs(curr, curr->child, originNext, visit);
curr->child = nullptr;
/* 原next指针在处理完子分支后会继续处理 */
if(originNext)
{
/* 如果已经记录visit，说明已经走到头，目前正在回溯状态 */
if(visit)
{
/* 直接传递visit作为prev，会导致该深度遍历栈后的所有prev出错，因为visit节点只能做一次prev，所以利用临时指针作为入参，而把visit置空 */
Node *tempVisit = visit;
visit = nullptr;
dfs(tempVisit, originNext, originNext->next, visit);
}
else
/* 如果visit为空，则正常遍历原next指针 */
dfs(curr, originNext, originNext->next, visit);
}
/* 修改每个节点的prev指针 */
curr->prev = prev;
/* 走到头了，回溯前记录该深度下的最后一个节点到visit指针 */
if(!curr->next && !curr->child)
visit = curr;
}
Node* flatten(Node* head) {
if(!head) return head;
Node *visit = nullptr;
dfs(nullptr, head, head->next, visit);
return head;
}
};官方题解解析
class Solution {
public:
Node* flatten(Node* head) {
function< Node*(Node*) > dfs = [&](Node* curr) {
Node* cur = curr;
/* 记录链表的最后一个节点，也就是我们前述的visit指针类似的作用 */
Node* last = nullptr;
while (cur) {
Node* next = cur->next;
// 如果有子节点，那么首先处理子节点
if (cur->child)
{
Node* child_last = dfs(cur->child);
/* 遍历子分支后，next会被改变，所以更新next, 提前记录下来后再把子分支的最后一个节点和当前next相连 */
next = cur->next;
// 将 curr 与 child 相连
cur->next = cur->child;
cur->child->prev = cur;
// 如果 next 不为空，就将 last 与 next 相连
if (next)
{
child_last->next = next;
next->prev = child_last;
}
// 将 child 置为空
cur->child = nullptr;
last = child_last;
}
else
last = cur;
cur = next;
}
return last;
};
dfs(head);
return head;
}
};回溯法
利用双向队列在每次进入子分支前，记录当前留下节点的next指针。先进后出。
class Solution {
public:
Node* flatten(Node* head) {
Node *curr = head, *prev = nullptr;
deque< Node *> stack{};
/* 只有当前节点为空，且队列里没有元素时，遍历工作才结束 */
while (curr || !stack.empty())
{
/* 当前为空时，表面已经到某一深度的最后一个结点，此时取出队列里的第一个next指针并连接 */
if (!curr)
{
curr = stack.front();
stack.pop_front();
curr->prev = prev;
prev->next = curr;
}
/* 进入子分支前，记录当前结点的next指针 */
if (curr->child)
{
if (curr->next)
stack.push_front(curr->next);
curr->child->prev = curr;
curr->next = curr->child;
/* 处理完子分支后置空 */
curr->child = nullptr;
}
/* 向前遍历 */
prev = curr;
curr = curr->next;
}
return head;
}
};