LeetCode解题分享：430. Flatten a Multilevel Doubly Linked List

Problem

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input:
1—2---3—4---5—6–NULL
   |
    7—8---9—10–NULL
      |
      11–12–NULL
Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

Explanation for the above example:

Given the following multilevel doubly linked list:

We should return the following flattened doubly linked list:

解题思路

   这一题的最基础的思路是使用深度优先搜索，遍历到一处节点时，如果它存在一个子节点，那么我们就进入它的子节点去进行搜索展开，然后返回展开之后的序列，插入到列表中，再接着遍历即可。

   代码如下：

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        return self.dfs(head)[0]

    def dfs(self, head):
        """
        return: head and tail
        """
        h = head
        prev = None
        while h:
            if h.child:
                tmp = h.next
                hh, tt = self.dfs(h.child)

                h.next = hh
                hh.prev = h

                tt.next = tmp
                if tmp:
                    tmp.prev = tt
                h.child = None
            else:
                prev = h
                h = h.next
        return head, prev