430. Flatten a Multilevel Doubly Linked List

Loading...LeetCode

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

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

Iterative

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

Recursive

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]