430. 扁平化多级双向链表

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

把链表旋转过来看做一棵树，前序遍历
参考了通过的代码
//迭代深搜

class Solution {
    func flatten(_ head: Node?) -> Node? {
        if head == nil {
            return nil
        }
        var nodeStack = [Node?]()
        let root: Node? = Node.init(-1)
        root?.next = head
        nodeStack.append(head)
        var prev = root, cur:Node? = nil
        while !nodeStack.isEmpty {
            cur = nodeStack.removeLast()
            prev?.next = cur
            cur?.prev = prev
            if cur?.next != nil {
                nodeStack.append(cur?.next)
            }
            if cur?.child != nil {
                nodeStack.append(cur?.child)
                cur?.child = nil
            }
            prev = cur
        }
        root?.next?.prev = nil
        return head
    }
}

//递归调用

class Solution {
    func flatten(_ head: Node?) -> Node? {
        var ptr = head ,nextPtr = head, Child = head
        while ptr != nil {
            if ptr?.child != nil {
                // 记住上一级链表的下一个位置
                nextPtr = ptr?.next
                // 移动指针到子链表头部
                Child = ptr?.child
                // 子链表头初始化，设置前一个指针位置
                Child?.prev = ptr
                //位于上一级链表的ptr开始指向子链表头部
                ptr?.next = Child
                //递归扁平化链表
                Child = flatten(Child)
                //遍历子链表
                while Child?.next != nil {
                    Child = Child?.next
                }
                //子链表走到末尾后指向上一级链表的下一处
                Child?.next = nextPtr
                //上一级链表的下一位置不为空
                //则设置它的前一个指针为当前子链表的头节点
                if nextPtr != nil {
                    nextPtr?.prev = Child
                }
                //此时位于上一级链表的ptr它的左侧单链表已访问
                ptr?.child = nil
                //移动ptr到上一级链表的下一个位置
                ptr = nextPtr
            }else{
                ptr = ptr?.next
            }
        }
        return head
    }
}