[LeetCode] 430. Flatten a Multilevel Doubly Linked List

原题链接： https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

1. 题目介绍

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.

给出一个双向链表的头节点，这个链表的节点除了 next 指针和 previous指针外，还有一个child指针。next指针指向下一个节点，previous指针指向前一个节点，child指针可能指向另外一个双向的链表，也即子链表。子链表可以有更多的子链表。
我们需要做的事情是构建一个多层的数据结构，就像范例中展示的那样。

把所有的链表的节点都放在一个双向链表中。这个双向链表不能有子链表。

Example:

Explanation for the above example:

Given the following multilevel doubly linked list:
原来的链表是这样的：

改变后的链表是这样子的：

2. 解题思路

把范例里面的链表看作一个树，不难看出答案是以深度优先搜索的方式遍历整个链表。这个题主要考察的还是深度优先搜索，只是借用了链表的外在形式。

所以解题思路是使用递归，以深度优先搜索的方式遍历整个链表。

实现代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    Node dummy = new Node();
	Node cur = dummy;

	public Node flatten(Node head) {
		dfs(head);
        return dummy.next;
    }

    public void dfs(Node root){
    	if (root == null) {
    		return;
    	}
        
        cur.next = new Node(root.val ,(cur == dummy ? null : cur), null , null);
    	cur = cur.next;
        
        dfs(root.child);
        dfs(root.next);
    }
}