*(1)Recursion*

```
class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL || root->left == NULL) //We may assume that it is a perfect binary tree,so (root->left == NULL) equal (root->left == NULL && root->right == NULL)
return;
root->left->next = root->right;
if (root->next != NULL)
root->right->next = root->next->left;
connect(root->left);
connect(root->right);
}
};
```

*(2)Iteration, the space complexity is O(1)*

```
class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL || root->left == NULL)
return;
TreeLinkNode *temp = root;
while(temp->left != NULL)
{
while (temp != NULL)//every time we just handle nodes in the same level,starting form the first node in current level
{
temp->left->next = temp->right;
if (temp->next != NULL)
temp->right->next = temp->next->left;
temp = temp->next;
}
root = root->left;
temp = root;
}
}
};
```

*(3)Using queue,it's very easy to understand although it doesn't meet the requirement.You can refer to the solution*

```
class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL) return;
queue<TreeLinkNode *>q;
int current_level = 0;//means total nodes in the current level
TreeLinkNode *node = NULL, *nodeRight = NULL;
q.push(root);
while (!q.empty())
{
current_level = q.size();
node = q.front();
q.pop();
--current_level;
while (true)
{
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
if (current_level == 0)
{
node->next = NULL;
break;
}
else
{
nodeRight = q.front();
q.pop();
--current_level;
node->next = nodeRight;
node = nodeRight;
}
}
}
}
};
```