Question：

Follow up for problem "

Populating Next Right Pointers in Each Node

".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• 
  You may only use constant extra space.
  

For example,


Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

Anwser 1：

/**
 * 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 *cur = root->next;
        TreeLinkNode *p = NULL;
        
        while(cur != NULL){     // find last right node (left or right)
            if(cur->left) {
                p = cur->left;
                break;
            }
            if(cur->right){
                p = cur->right;
                break;
            }
            cur = cur->next;
        }
        
        if(root->right){
            root->right->next = p;
        }
        
        if(root->left){
            root->left->next = root->right ? root->right : p;
        }
        
        connect(root->right);   // from right to left
        connect(root->left);
    }
};

注意点：

1） list为非完美二叉树，右分支可能为空，因此从right -> left 遍历

2） 从最右分支开始查找，且root没有 left 节点，则找 right 节点

Anwser 2：

/**
 * 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;    // save one line root(s)
        queue<TreeLinkNode *> Q2;   // save next one line root(s), swap with Q
        Q.push(root);
        
        while(!Q.empty()){
            TreeLinkNode *tmp = Q.front();
            Q.pop();
            
            if(tmp->left) Q2.push(tmp->left);
            if(tmp->right) Q2.push(tmp->right);
            
            if(Q.empty()){
                tmp->next = NULL;
                queue<TreeLinkNode*> tmpQ = Q;  // swap queue
                Q = Q2;
                Q2 = tmpQ;
            } else {
                tmp->next = Q.front();
            }
        }
    }
};

注意点：

1） 新增一个Q2队列，保存下一行的全部元素，辅助判断是最后一个元素（Q为空）则置为NULL

2） queue队列实现比递归要好

Anwser 3：

/**
 * 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;    // save one line root(s)
        Q.push(root);
        Q.push(NULL);       // flag
        
        while(!Q.empty()){
            TreeLinkNode *tmp = Q.front();
            Q.pop();
            
            if(tmp != NULL){        // check flag
                if(tmp->left) Q.push(tmp->left);
                if(tmp->right) Q.push(tmp->right);
                tmp->next = Q.front();
            } else {        
                if(Q.empty()){      // pop flag = NULL, then check is empty
                    break;
                }
               Q.push(NULL);
            }
        }
    }
};

注意点：

对比第二种方法，改进点是每一行结束处，采用NULL作为标志位