# 0430. Flatten a Multilevel Doubly Linked List
###### tags: `Leetcode` `Medium` `Bloomberg` `DFS`
Link: https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/
## 注意
做完dfs之后，要把child = null
## Code

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return head
        return self.dfs(head)
    def dfs(self, head):
        curr = head
        while curr and not curr.child:
            curr = curr.next
        if not curr:
            return head
        nextNode = curr.next
        childHead = self.dfs(curr.child)
        curr.child = None
        curr.next = childHead
        childHead.prev = curr
        while curr.next:
            curr = curr.next
        curr.next = nextNode
        if  nextNode: 
            nextNode.prev = curr
        return head

class Solution {
    public Node flatten(Node head) {
        if(head == null) return null;
        dfs(head);
        return head;
    }
    public Node dfs(Node head){
        Node curr = head;
        while(curr!=null && curr.child==null){
            curr = curr.next;
        }
        if(curr==null||curr.child==null) return head;
        Node tail = curr.next;
        Node next = dfs(curr.child);
        curr.child = null;
        curr.next = next;
        next.prev = curr;
        while(curr.next!=null){
            curr = curr.next;
        }
        curr.next = tail;
        if(tail != null) tail.prev = curr; 
        return head;
    }
}