Share my several solutions using C++,easy to understand

• (1)Recursion

``````class Solution {
public:
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:
if (root == NULL || root->left == NULL)
return;

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:
if (root == NULL) return;

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.