Question ：

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 to

NULL

.

Initially, all next pointers are set to

NULL

.

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

Anwser 1：

Travesal

/**
 * 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(NULL == root){
            return;
        }

        TreeLinkNode *left = root;
        while(left && left->left && left->right)
        {
            root = left;
            while(root)
            {
                root->left->next = root->right;     // connect two nodes of root
                if(root->next){
                    root->right->next = root->next->left;   // connect two isolated nodes
                }
                    
                root=root->next;    // traversal the same level line
            }
            left=left->left;
        }
    }
};

Anwser 2：

Recursive

/**
 * 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(NULL == root){
            return;
        }
        
        if(root->left){
            root->left->next = root->right;
        }
        
        if(root->right){
            root->right->next = root->next ? root->next->left : NULL;
        }

        connect(root->left);
        connect(root->right);
    }
};

Anwser 3：

Queue

/**
 * 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(NULL == root){
            return;
        }
        
        queue<TreeLinkNode *> Q;
        if(root != NULL){
            Q.push(root);
        }
        
        int row = 1;
        int count = 0;
        while(!Q.empty()){
            TreeLinkNode *tmp = Q.front();
            Q.pop();
            count++;
            
            if(tmp->left) Q.push(tmp->left);
            if(tmp->right) Q.push(tmp->right);
            
            if(count == row){
                tmp->next = NULL;
                count = 0;
                row *= 2;
            } else {
                tmp->next = Q.front();
            }
        }
    }
};

注意点：

1） Queue > Traversal > Recursive

2） Queue 没有递归的层次限制，可以使用很大的二叉树