多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:return head
        dummy=Node(None,None,None,None)
        self.preNode=dummy
        def dfs(curNode:Node):#前序遍历
            if not curNode:return 
            left=curNode.child#左边为孩子节点
            right=curNode.next#右边为正常的链表
            curNode.child=None#将孩子节点置空
            self.preNode.next=curNode#先遍历中间的，创建下一个链接
            curNode.prev=self.preNode#创建前一个链接
            self.preNode=curNode#遍历中间的
            dfs(left)#然后遍历左边的
            dfs(right)#再遍历右边的
        
        dfs(head)
        res=dummy.next
        res.prev=None
        return res