/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
void Solution::connect(TreeLinkNode* A) {
queue<TreeLinkNode*> q;
if(A!=NULL) {
q.push(A);
}
while(!q.empty()) {
int count = q.size();
for(int i=0;i<count-1;i++) { //all except the last in the level
TreeLinkNode* temp = q.front();
q.pop();
temp->next = q.front();
if(temp->left!=NULL){
q.push(temp->left);
}
if(temp->right!=NULL){
q.push(temp->right);
}
}
TreeLinkNode* temp = q.front();//last in the level
q.pop();
temp->next = NULL;
if(temp->left!=NULL){
q.push(temp->left);
}
if(temp->right!=NULL){
q.push(temp->right);
}
}
}