Programming Skills: Populating Next Right Pointers in Each Node

[Problem]

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/

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.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Example:

Given the following perfect binary tree,

After calling your function, the tree should look like:

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

中文翻譯:
給你一顆perfect binary tree，請幫每個node設定它的"next pointer"。next pointer要指向自己同一層的右兄弟(right sibling)，若此人不存在就設為NULL。

[Solution]

Use BFS to scan each level
Since each "next" should point to his right sibling, the most common way is to use BFS to find the right sibling.
During BFS, we will scan the tree level by level.
First, we put root node('1') into queue as level 1.
Then we put child nodes('2','3') of level 1 nodes into queue, and they are level 2 nodes.
Then we put child nodes('4','5','6','7') of level 2 nodes into queue, and they are level 3 nodes.
and so on...
During each level, we point 'next' to their sibling.


class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root) return;
        queue<TreeLinkNode*> q;

        q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){//scan this level
                TreeLinkNode* cur= q.front(); q.pop();
                cur->next = i==size-1 ? NULL : q.front();
                if(cur->left) q.push(cur->left);         
                if(cur->right) q.push(cur->right);    
            }
        }
    }
};

[Advance Solution]
The problem asked us to use "constant space". So the above solution did not meet the requirement, because the queue size is related to tree size.

Use the current level node to connect the node below current level.

Here is a brilliant O(1) space complexity solution from leetcode.
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37472/A-simple-accepted-solution

The key point is : since current node know who is 'next', we can use it to conncect current node's childs.
e.g.
Let's assume the node 1,2,3 is done. But the connection between 4,5,6,7 is not built yet.

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

To build the link between 4 and 5, I just : 2->left->next = 2->right
To build the link between 5 and 6, I just : 2->right->next = 2-->next->left
To build the link between 6 and 7, I just : 3->left->next = 3->right
To build the link between 7 and NULL, I don't need to do anything, default value of 7->next is NULL.

So we just need a pointer to go through node 1 to 7, and execute above procedure for each node.

Ok, let's write code.


     void connect(TreeLinkNode *root) {
        if(!root) return;
        TreeLinkNode* levelhead=root;
        TreeLinkNode* cur=root;
        while(levelhead->left){ // for each level
            cur=levelhead;//'cur' will go throught each node in this level
            while(cur){
                cur->left->next  = cur->right;
                if(cur->next)
                    cur->right->next = cur->next->left;
                cur=cur->next;
            }
            levelhead=levelhead->left;        
        }
     }