1
// method-1
2
class Solution {
3
 public:
4
  Node *connect(Node *root) {
5
    if (!root) return NULL;
6
    queue<Node *> q;
7
    q.push(root);
8
    root->next = NULL;
9

10
    while (!q.empty()) {
11
      int size = q.size();
12
      Node *prev = NULL;
13

14
      for (int i = 0; i < size; i++) {
15
        Node *temp = q.front();
16
        q.pop();
17

18
        if (prev) prev->next = temp;
19

20
        if (i == size - 1) {
21
          temp->next = NULL;
22
        }
23

24
        if (temp->left) q.push(temp->left);
25

26
        if (temp->right) q.push(temp->right);
27

28
        prev = temp;
29
      }
30
    }
31

32
    return root;
33
  }
34
};