Populating Next Right Pointers in Each Node

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

分析：看到此题想到树的层次遍历，但是层次遍历需要用队列保留上一层的结点，但是如何区分结点是否是在一层呢，想到用两个队列，一个保留上层结点，一个下层结点，每次从队列弹出一个结点，将该结点的左右孩子压入下层队列，当上层队列为空时，最后弹出的结点的next为NULL。

Accepted，但是感觉所用空间不是常数空间，是和输入的树有关的。

代码如下：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL){
            return;
        }
        root->next = NULL;
        queue<TreeLinkNode*> queue1;
        queue<TreeLinkNode*> queue2;
        queue1.push(root);
        while(!queue1.empty()){
            TreeLinkNode* node = queue1.front();
			queue1.pop();
            if(node->left){
                queue2.push(node->left);
                queue2.push(node->right);
            }
            if(queue1.empty()){
                node->next = NULL;
                if(queue2.empty()){
                    break;
                }else{
                    queue1.swap(queue2);
                }
               
            }else{
                node->next = queue1.front();
            }
        }
        
    }
};

改进：搜索别人方法，找到一种需要常数空间的方法，采用按层遍历的方法，每次将每一层的最左边结点开始，按next遍历，将下一层的连接起来。

class Solution {  
public:  
    void connect(TreeLinkNode *root) {  
        if(root == NULL){
            return;
        }
        
        while(root && root->left){
            TreeLinkNode* node = root->left;
            while(root){
                root->left->next = root->right;
                if(root->next){
                    root->right->next = root->next->left;
                }
                root = root->next;
            }
            root = node;
        }
   }  
}; 

2、Populating Next Right Pointers in Each Node II

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

分析：看到此题就是将上述改为普通的二叉树了，上一题的第一种双队列方法照样可以，

如下：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL){
            return;
        }
        root->next = NULL;
        queue<TreeLinkNode*> queue1;
        queue<TreeLinkNode*> queue2;
        queue1.push(root);
        while(!queue1.empty()){
            TreeLinkNode* node = queue1.front();
			queue1.pop();
            if(node->left){
                queue2.push(node->left);
            }
            if(node->right){
                queue2.push(node->right);
            }
            if(queue1.empty()){
                node->next = NULL;
                if(queue2.empty()){
                    break;
                }else{
                    queue1.swap(queue2);
                }
               
            }else{
                node->next = queue1.front();
            }
        }
        
    }
};

按第一题的第二种方法如下所示：

class Solution {  
public:  
    void connect(TreeLinkNode *root) {  
        if(root == NULL){
            return;
        }
        TreeLinkNode* node;
        while(1){
             //找到下层第一个有孩子的结点
            while(root && !root->left && !root->right){
                root = root->next;
            }
            if(!root){
                return;
            }
            //保存下层最左边结点
            if(root->left){
                node = root->left;
            }else{
                node = root->right;
            }
            //将此层的指针连接起来
            TreeLinkNode* lastNode = NULL;
            while(root){
                if(root->left){
                    if(lastNode){
                         lastNode->next = root->left;
                    }
                    if(root->right){
                        root->left->next = root->right;
                        lastNode = root->right;
                    }else{
                        lastNode = root->left;
                    }
                }else if(root->right){
                    if(lastNode){
                         lastNode->next = root->right;
                    }
                    lastNode = root->right;
                }
                root = root->next;
            }
            root = node; //下层开始
        }
   }  
};