I have this tree structure, where each node has a next and child pointer. I am trying to flatten such a tree to a linked list where each node only uses the next pointer.

我有这个树结构，其中每个节点都有一个下一个和子指针。我正在尝试将这样的树展平为链表，其中每个节点只使用下一个指针。

Example input:

示例输入：

1 --> 2 --> 3 --> 4 --> 5 --> 6
            |
            V 
            7 --> 8 -- > 9 --> 10
                  |
                  V
                  11 --> 12

Expected output:

预期产出：

  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12

This is my code:

这是我的代码：

struct ListNode {
    int val;
    struct ListNode* next;
    struct ListNode* child;

    ListNode(int x) {
        val = x;
        next = NULL;
        child = NULL;
    }
};

ListNode* flatten(ListNode* head) {
    ListNode *temp = head, *r = NULL;
    while (temp) {
        if (temp->child) {
            r = temp->next;
            temp->next = flatten(temp->child);
        }
        if (!temp->next && r) {
            temp->next = r;
            r = NULL;
        }
        temp = temp->next;
    }
    return head;
}

Problem

When I provide it the example input, my code gets into infinite recursion.

当我为它提供示例输入时，我的代码进入无限递归。

Where is my mistake?

我的错误在哪里？

Your code does not get into infinite recursion, but into an infinite loop.

您的代码不会进入无限递归，而是进入无限循环。

There are these issues:

存在以下问题：

• The child pointers are never cleared to nullptr, and so you get nodes that have both their child and next pointing to the same node. As you also link back tail nodes to nodes in upper "levels", this eventually leads to revisits of the same child nodes over and over again. Things would not get into such cycles if you would clear child pointers with temp->child = nullptr; right after the recursive call comes back.

  子指针永远不会被清除到nullptr，因此您会得到子节点和Next都指向同一节点的节点。由于您还将尾节点链接回较高“级别”中的节点，这最终会导致反复访问相同的子节点。如果您在递归调用返回之后使用temp->Child=nullptr；清除子指针，事情就不会进入这样的循环。

  
  



• Although r saves a pointer to be reused later, there is no provision for when multiple nodes in the same "horizontal" list have a non-null child pointer: your loop can only remember one of them in r, and so you will lose information.

  尽管r保存了一个指针以备以后重用，但当同一“水平”列表中的多个节点具有非空子指针时，并没有提供这样的规定：您的循环只能记住r中的一个节点，因此您将丢失信息。

  
  



• The logic gives precedence to linking child lists, coming back to the "calling" list after child lists have been wired into the current list. Yet your desired output gives precedence to the next lists, wanting to put child nodes after those. I'll assume this part of the code is wrong, and your description of the expected output is right.

  逻辑优先于链接子列表，在子列表连接到当前列表之后返回到“呼叫”列表。然而，您想要的输出优先于下一个列表，希望将子节点放在这些列表之后。我将假定这部分代码是错误的，并且您对预期输出的描述是正确的。

  
  

You can do this without recursion by just keeping track of the current tail of the part of the list that is being flattened, while the temporary pointer walks behind it to move and clean up the child pointers it encounters on its way.

您可以在没有递归的情况下做到这一点，只需跟踪正在被展平的列表部分的当前尾部，而临时指针在其后面移动并清理它在途中遇到的子指针。

ListNode* getTail(ListNode* head) { // Assumes non-null argument
    while (head->next) {
        head = head->next;
    }
    return head;
}

ListNode* flatten(ListNode* head) {
    ListNode *tail = getTail(head);
    for (ListNode *node = head; node; node = node->next) {
        tail->next = node->child;
        tail = getTail(tail);
        node->child = nullptr;
    }
    return head;
}

Unrelated to your question, but in C++:

与您的问题无关，但在C++中：

• you should not use NULL but nullptr


• struct ListNode can just be ListNode


• You can use the shorter Member Initializer List syntax for your constructor.

So:

所以：

struct ListNode {
    int val;
    ListNode* next = nullptr;
    ListNode* child = nullptr;

    ListNode(int x): val(x) {}
}

Finally, flatten will always return the argument given to it, so you could consider making it a void function.

最后，Flatten将始终返回提供给它的参数，因此您可以考虑将其设置为空函数。