# 430. Flatten a Multilevel Doubly Linked List

{% embed url="<https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/>" %}

看图就能明白过来，其实就是把`tree-like`变成`array-like`，而且从结果看出不是`BFS`层序遍历，是`DFS Preorder`，那就直接上`stack`解决，因为是链表涉及到前后连接，需要用两个指针一起移动。

12/29/2020 Update: 也可以直接 recursive traverse 记录所有 node 的值，再挨个连接起来。

{% tabs %}
{% tab title="Iterative" %}

```python
class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head: return None
        dummy = Node(0, None, head, None)
        stack = collections.deque([head])
        prev = dummy
        while stack:
            cur = stack.pop()
            prev.next = cur
            cur.prev = prev
            if cur.next: 
                stack.append(cur.next)
            if cur.child:
                stack.append(cur.child)
                cur.child = None
            prev = cur
        res = dummy.next
        res.prev = None
        return res
```

{% endtab %}

{% tab title="Recursive" %}

```python
class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head: return None
        traverse = []
        
        def preorder(node):
            if not node: return
            traverse.append(Node(node.val, None, None, None))
            preorder(node.child)
            preorder(node.next)
        
        preorder(head)
        
        for i in range(1, len(traverse)):
            traverse[i].prev = traverse[i-1]
            traverse[i-1].next = traverse[i]
            
        return traverse[0]
```

{% endtab %}
{% endtabs %}
