O(1) space O(n) complexity Iterative Solution with Explanation

• We build a linked list for each row, level by level, from top to bottom.

We start from the first level, there is only an element: root, it's already a linked list which only contains an element.

We use a variable current to make the pointer of the current rows linked list. We can use current = current.next to iterate the whole list.

Now we will build the linked list for next row. We use nextRowDummyHead to represent the sentinel of the linked list, so nextRowDummyHead.next will be the head of the linked list. We use nextRowCurrentNode to represent the current node.

We check the left and right children for each current, we can link them to the tail of the next row's linked list.

while (current != null) {

while (current != null) {

// if left child is not null, link it to the tail
if (current.left != null) {
nextRowCurrentNode.next = current.left;
nextRowCurrentNode = nextRowCurrentNode.next;
}

// link the right node to the tail if it's not null
if (current.right != null) {
nextRowCurrentNode.next = current.right;
nextRowCurrentNode = nextRowCurrentNode.next;
}
// move to next
current = current.next;
}

// move to next level