Given a binary tree. Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Iterative Solution: (using Level Order Traversal)
class Solution
{
public:
Node *connect(Node *root)
{
if (root == NULL)
{
return root;
}
queue<Node *> q;
q.push(root);
q.push(NULL);
Node *t = NULL;
while (!q.empty())
{
t = q.front();
q.pop();
if (t != NULL)
{
t->next = q.front();
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}
}
else if (!q.empty())
{
q.push(NULL);
}
}
return root;
}
};
