Given a binary tree

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL
.
Initially, all next pointers are set toNULL
.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,Given the following perfect binary tree,

    1
   /  \
  2    3
 / \  / \
4  5  6  7

After calling your function, the tree should look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

/**
 * 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) {
        while(root!=NULL)
        {
            TreeLinkNode* next = NULL;
            TreeLinkNode* pre = NULL;
            for(;root!=NULL;root=root->next) //遍历的原因是root是一个链表
            {
                if(next==NULL)
                   next = (root->left != NULL) ? root->left : root->right;
                  
                if(root->left)
                {
                    if(pre)
                      pre->next = root->left;
                    pre = root->left;
                }
                
                if(root->right)
                {
                    if(pre)
                      pre->next = root->right;
                    pre = root->right;
                }
                
            }
            root = next;
        }
    }
};