java - 在这个“扁平化双向链表”代码中，递归是如何工作的？

Question

问题来自 leetcode #430 Flatten a Multilevel 双链表。所以基本上，每个节点都有三个字段：next、prev 和 child。问题要求展平给定的链表。

public Node flatten(Node head) {
    flattenHelper(head);
    return head;
}

public Node flattenHelper(Node head){
    if(head.next == null){
        //return if reach the tail
        System.out.println("returned " + head.val);
        return head;
    }
    if(head.child != null){
        Node prevNext = head.next;

        //link current node's next field to its child
        head.next = head.child;
        head.child = null;
        head.next.prev = head;

        //the tail of the child linked-list
        Node children = flatten(head.next);
        children.next = prevNext;
        prevNext.prev = children;
    }
    Node x = flatten(head.next);
    System.out.println("current Node value: " + head.val + " returned from the bottom: " + x.val);
    return x;
}

我知道有更好的方法来解决这个问题，但为什么这段代码不起作用？

根据我对递归的理解，最底层堆栈的返回值应该通过 传递给它的调用者堆栈Node x = flatten(head.next); return x;，并最终到达Node children = flatten(head.next);连接。

但是，在堆栈向上的过程中，Node x = flatten(head.next); return x;返回当前节点下一个堆栈的节点，而不是从最底部堆栈返回的节点。

示例测试用例

System.out.printlns

非常感谢您的帮助！

标签： javarecursion