关于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;    }};