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;
}
}
}
