Java O(1) space solution (no recursion, no queues), explained by comments


#1
public class Solution {
    public void connect(TreeLinkNode root) {
        // Main idea: we go level-by-level with 3 pointers:
        // a pointer for the current node on the current level, and two
        // pointers for the level below: the head and the last node.
        // We use the 'next' pointers to traverse level i, and
        // in the meantime we set the 'next' pointers on level i+1.
        TreeLinkNode current = root; // Current node processed
        TreeLinkNode nextHead = null; // Head of the level below
        TreeLinkNode nextLast = null; // Current rightmost on level below
        while (current != null) { // Traverse each level
        
            while (current!= null) { // Traverse each node on the given level
                // Check first children
                if (current.left != null) {
                    // If next head does not exist make new head
                    if (nextHead == null) nextHead = current.left;
                    // If next head exists, rightmost must also exist, connect to that
                    else nextLast.next = current.left;
                    // Overwrite rightmost regardless of head
                    nextLast = current.left;
                }
                // Check second children
                if (current.right != null) {
                    // If next head does not exist make new head
                    if (nextHead == null) nextHead = current.right;
                    // If next head exists, rightmost must also exist, connect to that
                    else nextLast.next = current.right;
                    // Overwrite rightmost regardless of head
                    nextLast = current.right;
                }
                // Move node to its next (if it exists, it was set when processing
                // the level above)
                current = current.next;
            }
            // End of level
            
            // Start new level
            current = nextHead;
            // Clear next
            nextHead = nextLast = null;
        }
    }
}