430. Flatten a Multilevel Doubly Linked List

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
class Solution(object):
    '''
    def flatten(self, head):
        if head is None:
            return head
        
        dummy = Node(-1, None, None, None)
        stack = []
        stack.append(head)
        cur = dummy
        while(len(stack) != 0):
            top = stack.pop()
            cur.next = top
            cur.child = None
            top.prev = cur
            if top.next:
                stack.append(top.next)
            if top.child:
                stack.append(top.child)
            top.child = None
            cur = cur.next
        
        dummy.next.prev = None # break the dummy link is critical
        return dummy.next
    '''
    def flatten(self, head):
        if head is None:
            return head
        
        dummy = Node(-1, None, None, None)
        tail = self.helper(dummy, head)
        dummy.next.prev = None # break the dummy link is critical
        return dummy.next
        
    def helper(self, cur, head):
        if head is None:
            return cur
        
        # self 
        cur.next = Node(head.val, cur, None, None)
        cur = cur.next
        # left -- child
        cur = self.helper(cur, head.child)
        # right -- next
        cur = self.helper(cur, head.next)
        return cur

• 从特殊问题抽象为简单问题 ---- 带 parent 的二叉树 DFS 前序遍历

• 用 Stack 处理 recursion，先出的要后推入栈中

• 审题 审题 审题 Node is now Node(val, prev, child, next)

• 如果使用dummy node或任何题目不涉及的辅助项，用完后要 double check dummy 项是否对结果有影响。像这里的 dummy.next.prev = None 就困扰了两天