LeetCode 420 扁平化多级双向链表 （深搜、双向链表）

扁平化多级双向链表

class Solution {
    // 头部哑结点
    Node header = new Node();
    Node cur;
    public Node flatten(Node head) {
        if(head == null) return null;
        cur = header;
        helper(head);
        // 第一个节点的前驱必须为空
        header.next.prev = null;
        return header.next;
    }

    // 深度优先搜索 —— 先序遍历
    public void helper(Node node){
        if(node == null) return;
        // 接上链表
        cur.next = node;
        node.prev = cur;
        cur = cur.next;

        // 注意这里的 node的next之后会发生改变，所以要预存下来
        Node temp = node.next;
        helper(node.child);
        // 题目要求双向链表中的child域为空
        node.child = null;
        helper(temp);
    }
}