430. 扁平化多级双向链表(Medium)

Python示例

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        def dfs(head):
            if head.child:
                end = dfs(head.child)
                if head.next: # 如果有后续节点
                    end.next = head.next 
                    end.next.prev = end 
                head.next = head.child
                head.child.prev = head 
                head.child = None # 删除子节点
            if head.next:
                return dfs(head.next)
            else:
                return head 
        if not head: 
            return head 
        dfs(head)
        return head

Go示例

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Prev *Node
 *     Next *Node
 *     Child *Node
 * }
 */
func dfs(root *Node) *Node {
    var after *Node
    if root.Child != nil { // 如果有孩子节点，先处理孩子节点
        after = dfs(root.Child) // 找到最后一个孩子
        if root.Next != nil {
            after.Next = root.Next // 最后一个孩子指向下一个节点
            after.Next.Prev = after
        }
        root.Next = root.Child // 都是成对修改的
        root.Child.Prev = root 
        root.Child = nil // 删除节点
    }

    if root.Next == nil { // 如果自己是尾巴节点
        return root 
    }

    return dfs(root.Next)

}
func flatten(root *Node) *Node {
    if root == nil {
        return root
    }

    dfs(root)
    return root 
}