116. Populating Next Right Pointers in Each Node

My simple solution as following:

1:  class Solution {  
2:  public:  
3:    void connect(TreeLinkNode *root) {  
4:      while (root) {  
5:        TreeLinkNode *q = root;  
6:        while (q && q->left) {  
7:          q->left->next = q->right;  
8:          if (q->next) q->right->next = q->next->left;  
9:          q = q->next;  
10:        }  
11:        root = root->left;  
12:      }  
13:      return;  
14:    }  
15:  };  

Here is the DFS solution which also meets the requirement of constant space.

1:  /**  
2:   * Definition for binary tree with next pointer.  
3:   * struct TreeLinkNode {  
4:   * int val;  
5:   * TreeLinkNode *left, *right, *next;  
6:   * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    void connect(TreeLinkNode *root) {  
12:      if (root == NULL || root->left == NULL) return;  
13:      TreeLinkNode *cur = root, *prev = NULL;  
14:      while (cur) {  
15:        cur->left->next = cur->right;  
16:        if (prev != NULL) prev->next = cur->left;  
17:        prev = cur->right;  
18:        cur = cur->next;  
19:      }  
20:      connect(root->left);  
21:    }  
22:  };