1
class Solution {
2
  public Node connect(Node root) {
3
    if (root == null) {
4
      return root;
5
    }
6
    Node head = null; // the start node of next level, the first left of next level
7
    Node prev = null; // the next pointer
8
    Node curr = root;
9

10
    while (curr != null) {
11
      // traverse the whole current level, left -> right, until we meet a null pointer
12
      while (curr != null) {
13
        if (curr.left != null) {
14
          if (head == null) {
15
            head = curr.left;
16
            prev = curr.left;
17
          } else {
18
            prev.next = curr.left;
19
            prev = prev.next;
20
          }
21
        }
22

23
        if (curr.right != null) {
24
          if (head == null) {
25
            head = curr.right;
26
            prev = curr.right;
27
          } else {
28
            prev.next = curr.right;
29
            prev = prev.next;
30
          }
31
        }
32
        curr = curr.next;
33
      }
34

35
      curr = head;
36
      prev = null;
37
      head = null;
38
    }
39
    return root;
40
  }
41
}