# Java Solution with O(n) time and O(1) space (27 lines)

• Once you got the basic idea, it is easy to understand this solution.

The most important thing to realize is that:

For example,

``````     1 -> NULL        level 1
/  \
2 -> 3 -> NULL     level 2
/ \    \
4-> 5 -> 7 -> NULL    level 3
``````

Consider this tree. At first, link `root` to `null`; Thus level 1 is a linked list. Then we move on to level 2; and sicne level 1 is already a linked list, we can iterate each node in the linked list (just one node except null at this level), and link the children from left to right (), then link to `null` at the end. Moving on to level 3; level 2 is already a linked list, so we iterate each node (`2`, and `3`), link their children from left to right (skip if the children is null, such as the left child of node `3`), then link to `null` at the end. Same idea applies beyond.

Thus, we just need to iterate each element of the above level, link their left and right nodes (if it has) in order, and then iterate through each level.

The Java code is attached below: (~ 27 lines) It uses `O(n)` time and `O(1)` space.

``````public class Solution {
if (root == null) {
return;
}
root.next = null;
cur = dummy;
cur = cur.next;
}