关于leetcode算法:Leetcode-430-扁平化多级双向链表

430. 扁平化多级双向链表

写在后面：
最近事件比拟多，马上要筹备期末考试了，当初是在温习。而后又有数据库课设和计算机组成原理课设，好多事件要做，还有马上就要考六级口试了，每天都要刷英语题，然而做算法题我是肯定会坚持下去的，心愿大家能够和我一起致力，谢谢大家。
原题链接：
https://leetcode.cn/problems/…leetcode 430. 扁平化多级双向链表
题目形容：
你会失去一个双链表，其中蕴含的节点有一个下一个指针、一个前一个指针和一个额定的子指针。这个子指针可能指向一个独自的双向链表，也蕴含这些非凡的节点。这些子列表能够有一个或多个本人的子列表，以此类推，以生成如上面的示例所示的多层数据结构给定链表的头节点 head, 将链表扁平化，以便所有节点都呈现在单层双链表中。让 crr 是一个带有子列表的节点。子列表中的节点应该呈现在扁平化列表中的 curr 之后和 curr.next 之前。返回扁平列表的 had。列表中的节点必须将其所有子指针设置为 NULL。
最开始题目我感觉有点难了解，要看好几遍才能够了解，我倡议你关上链接间接看 leetcode 外面的题目形容，我这里写的不是很分明。
示例：

做题思路

深度优先遍历的思维，我这里用的栈来写深度优先遍历，没有用队列，遇到一个节点 cur，if(cur->child==NULL)cur=dfs(cur->next); else{递归搜寻到孩子节点为头节点的链表的尾部，将这几个点连贯好（这里我用一张图来示意）；}

留神：因为是双向链表，要批改连贯的中央有四个。而后 t1,t2 别离是是孩子链表上的头和尾节点。

代码 c ++ 版

class Solution {
public:
    Node* dfs(Node* now){if(now==NULL) return NULL;
        Node* ans=NULL;
        if(now->child==NULL){if(now->next==NULL) return now;
            ans=dfs(now->next);
        }
        else{
            Node* t1=now->child;
            Node* t2=dfs(now->child);
            Node* t3=now->next;
            now->child=NULL;
            now->next=t1;
            t1->prev=now;
            t2->next=t3;
            if(t3==NULL) return t2;
            else t3->prev=t2;
            ans=dfs(t3);
        }
        return ans;
    }
    Node* flatten(Node* head) {dfs(head);
        return head;
    }
};