** 
 * 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) {} 
 * }; 
 */  
class Solution {  
public:  
    void connect(TreeLinkNode *root) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        if(root == NULL) return ;  
        root->next = NULL;  
        TreeLinkNode* prevHead = root;  
        while(true)  
        {  
            TreeLinkNode* cur = prevHead;  
            TreeLinkNode* prev = NULL;  
            while(cur != NULL)  
            {  
                if(cur->left != NULL)  
                {  
                    if(prev != NULL) prev->next = cur->left, prev = prev->next;  
                    else prev = cur->left, prevHead = prev;  
                }  
                if(cur->right != NULL)  
                {  
                    if(prev != NULL) prev->next = cur->right, prev = prev->next;  
                    else prev = cur->right, prevHead = prev;  
                }  
                cur = cur->next;  
            }  
            if(prev != NULL) prev->next = NULL;  
            else break;  
        }  
    }  
};