Блог

Проблема заключается в том, что leetcode # 430 сглаживает многоуровневый двусвязный список. Таким образом, по сути, каждый узел имеет три поля: 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 Система.выход.печать

Большое вам спасибо за помощь!