java - 将二叉树展平为链表

Question

你好我目前正在尝试解决这个问题(不幸的是，没有解决方案):

http://blog.gainlo.co/index.php/2016/06/12/flatten-a-linked-list/

基本上，您想要展平具有指向单向链表的next 指针和down 指针的链表。

下面是我想出的，如果有任何错误或者如果您发现任何会破坏它的边缘情况，请纠正我。

static class Node {
    Node next;
    Node down;
    int val;
    Node(int val) {
        this.val = val;
    }
}

static Node flattenLinkedList(Node head) {
    Queue<Node> q = new LinkedList<>();
    q.add(head);
    Node dummyhead = new Node(0);
    Node pre = dummyhead;
    while (!q.isEmpty()) {
        Node current = q.poll();
        while (current != null) {
            pre.next = new Node(current.val);
            pre = pre.next;
            if (current.down != null) {
                q.add(current.down);
            }
            current = current.next;
        }
    }
    return dummyhead.next;
}

public static void main(String[] args) {
    Node start = new Node(1);
    start.next = new Node(2);
    start.next.next = new Node(3);
    start.next.next.next = new Node(4);
    start.next.down = new Node(5);
    start.next.down.down = new Node(8);
    start.next.down.next = new Node(6);
    start.next.next.next.down = new Node(7);

    Node sol = flattenLinkedList(start);
}

P.S 我这样做是为了面试练习，而不是为了作业。

Answer 1

public static Node flatten(Node n) {
    if (n==null) return n;

    Node p = n;

    while (p!=null) {
        if (p.down != null)  {
            Node pn = p.next;
            p.next = flatten(p.down);
            while (p.next!=null) {
                p = p.next;
            }
            p.next = pn;
        }
        p = p.next;
    }

    return n;
}