Populating Next Right Pointers in Each Node Solutions in C++

// Source : https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
// Author : Hao Chen
// Date   : 2014-06-19



#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

/**
 * 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) {}
    TreeLinkNode() : val(0), left(NULL), right(NULL), next(NULL) {}
};


void connect(TreeLinkNode *root) {

    if (root==NULL){
        return;
    }
    if (root->left && root->right){
        root->left->next = root->right;
    }
    if (root->next && root->right){
        root->right->next = root->next->left;
    }
    connect(root->left);
    connect(root->right);

}

void connect1(TreeLinkNode *root) {

    if (root==NULL){
        return;
    }

    vector<TreeLinkNode*> v;    
    v.push_back(root);
    int i = 0;
    
    while (i < v.size()){
        if (v[i]->left){
            v.push_back(v[i]->left);
        }
        if (v[i]->right) {
            v.push_back(v[i]->right);
        }
        i++;
    }

    i=1;
    while(i<v.size()){
        for (int j=i-1; j<2*(i-1); j++){
           v[j]->next = v[j+1]; 
        }
        i *= 2; 
    }

}

void connect2(TreeLinkNode *root) {

    if (root==NULL){
        return;
    }
    
    vector<TreeLinkNode*> v;

    v.push_back(root);
    
    while(v.size()>0){
        
        if (root->left && root->right && root->left->next == NULL ) {
            root->left->next = root->right;
            
            if (root->next){
                root->right->next = root->next->left;
            }
            
            v.push_back(root->right);
            v.push_back(root->left);
        }
        root=v.back();
        v.pop_back();
    }
}

void connect3(TreeLinkNode *root) {
    if(root == NULL) return;

    queue<TreeLinkNode*> q;
    TreeLinkNode *prev, *last;
    prev = last = root;

    q.push(root);
    while(!q.empty()) {
        TreeLinkNode* p = q.front();
        q.pop();

        prev->next = p;
        if(p->left ) q.push(p->left);
        if(p->right) q.push(p->right);

        if(p == last) { // meets last of current level
            // now, q contains all nodes of next level
            last = q.back();
            p->next = NULL; // cut down.
            prev = q.front();
        }
        else {
            prev = p;
        }
    }
}

// constant space
// key point: we can use `next` pointer to represent
//      the buffering queue of level order traversal.
void connect4(TreeLinkNode *root) {
    if(root == NULL) return;

    TreeLinkNode *head, *tail;
    TreeLinkNode *prev, *last;

    head = tail = NULL;
    prev = last = root;

#define push(p) \
    if(head == NULL) { head = tail = p; } \
    else { tail->next = p; tail = p; }

    push(root);
    while(head != NULL) {
        TreeLinkNode* p = head;
        head = head->next; // pop

        prev->next = p;
        if(p->left ) push(p->left);
        if(p->right) push(p->right);

        if(p == last) {
            last = tail;
            p->next = NULL; // cut down.
            prev = head;
        }
        else {
            prev = p;
        }
    }
#undef push
}

void printTree(TreeLinkNode *root){
    if (root == NULL){
        return;
    }
    printf("[%d], left[%d], right[%d], next[%d]\n", 
            root->val, 
            root->left ? root->left->val : -1, 
            root->right ? root->right->val : -1, 
            root->next?root->next->val : -1 );    

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

int main()
{
    const int cnt = 7; 
    TreeLinkNode a[cnt];
    for(int i=0; i<cnt; i++){
        a[i].val = i+1;
    } 

    
    for(int i=0, pos=0;  pos < cnt-1; i++ ){
        a[i].left = &a[++pos];
        a[i].right = &a[++pos];
    }
    
    connect(&a[0]); 

    printTree(&a[0]);

    return 0;
}

#include <stack>

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) {
        if (root == NULL) return;
        while (root->left)
        {
            root->left->next = root->right;
            for (TreeLinkNode *cur = root; cur->next; cur = cur->next)
            {
                cur->right->next = cur->next->left;
                cur->next->left->next = cur->next->right;
            }
            root = root->left;
        }
    }
};

/// Source : https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/
/// Author : liuyubobobo
/// Time   : 2018-10-08

#include <iostream>
#include <queue>
#include <cassert>

using namespace std;


/// Using queue for BFS
/// Time Complexity: O(n)
/// Space Compelxity: O(n)

/// 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) {

        if(!root) return;

        queue<TreeLinkNode*> q;
        q.push(root);
        int level = 0;
        while(!q.empty()){
            int n = (1 << level);
            while(n --){
                TreeLinkNode* cur = q.front();
                q.pop();
                if(n)
                    cur->next = q.front();
                if(cur->left){
                    q.push(cur->left);
                    assert(cur->right);
                    q.push(cur->right);
                }
            }
            level ++;
        }
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/
/// Author : liuyubobobo
/// Time   : 2018-10-08

#include <iostream>
#include <queue>
#include <cassert>

using namespace std;


/// DFS
/// Time Complexity: O(n)
/// Space Compelxity: O(logn)

/// 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) {

        if(!root || !root->left) return;
        dfs(root->left, root->right);

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

private:
    void dfs(TreeLinkNode* l, TreeLinkNode* r){

        if(l){
            l->next = r;
            dfs(l->right, r->left);
        }
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/
/// Author : liuyubobobo
/// Time   : 2018-10-19

#include <iostream>
#include <queue>
#include <cassert>

using namespace std;


/// BFS without queue
/// Since the upper level have already been a linked list
/// We can traverse the upper level in a linked list way to connect the lower level
/// Actually, the upper linked list is our queue :-)
///
/// Time Complexity: O(n)
/// Space Compelxity: O(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) {

        if(!root) return;

        while(root->left){
            TreeLinkNode* p = root;
            TreeLinkNode* dummyHead = new TreeLinkNode(-1);
            TreeLinkNode* cur = dummyHead;
            while(p){
                cur->next = p->left;
                cur = cur->next;

                cur->next = p->right;
                cur = cur->next;

                p = p->next;
            }

            delete dummyHead;
            root = root->left;
        }
    }
};


int main() {

    return 0;
}