[数据结构与算法]扁平化多级双向链表/Leedcode/源码/C++

430. 扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

输出：[1,2,3,7,8,11,12,9,10,4,5,6]

解释：

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

输入的多级列表如下图所示：

扁平化后的链表如下图：

将脖子歪45°，可以简单看出扁平化相当于先序遍历一个树，树的遍历具体可见我的另一个文章（https://blog.csdn.net/mountains_L/article/details/115304102），但是这只是本题第一个简单的难点。

根据链接的代码先序遍历树，在此过程中将结点重排，如下代码

Node* flatten(Node* head) {
    stack<Node*> s;
    Node* p = head;
    Node* pre = NULL;
    while (p || !s.empty()) {
        while (p) { //进入左子树最下
            s.push(p); //入栈
            if(pre != NULL) pre->next = p;
            p->prev = pre;
            pre = p;
            p = p->child;
            pre->child = NULL;
        }
        if (!s.empty()) {
            p = s.top(); //出栈
            s.pop();
            p = p->next;
        }
    }
    return head;
}

乍一看感觉挺对的，但是跑一下就发现是错的，问题出在下图语句1处，以实例为例，p指向结点7时，pre为3，3->next被修改为7，在结点7遍历之后将回溯到结点3时，需要在语句2处进入3->next，这时就又前往3，而不是原来的4了。

那么，如何做到既修改了先序遍历中父节点的next（rchild），又能在回溯到父节点时能顺利进入next（rchild）呢？有一个办法，在入栈时（语句3）不记录父节点，而直接记录next（rchild），在回溯时不从父节点进入next（rchild），而直接进入next（rchild）（反正前序遍历，父节点在右孩子之前已被遍历，父节点无用）。这样就可以随心所欲的改变父节点的next（rchild）。全部源码如下图所示：

Node* flatten(Node* head) {
    stack<Node*> s;
    Node* p = head;
    Node* pre = NULL;
    while (p || !s.empty()) {
        while (p) { //进入左子树最下
            if(p->next) s.push(p->next); //入栈
            if(pre != NULL) pre->next = p;
            p->prev = pre;
            pre = p;
            p = p->child;
            pre->child = NULL;
        }
        if (!s.empty()) {
            p = s.top(); //出栈
            s.pop();
        }
    }
    return head;
}