117. Populating Next Right Pointers in Each Node II

Similar to "Populating Next Right Pointers in Each Node I", we need to track current level nodes and next level starting node. All we need to do is to scan the current level nodes and sort out the next level nodes. The difference is that the given tree is not complete anymore, which means when sorting out the next level, we can't assume that left child's next is right child and right child's next is the left child of the next node in current level. Therefore, we need to use a new pointer to track the previous node. Other than this algorithm, we definitely can do level order traversal but the problem requires 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:      TreeLinkNode *cur = root, *prev = NULL, *next = NULL;  
13:      while (cur) {  
14:        while (cur) {  
15:          if (cur->left) {  
16:            if (prev != NULL) {  
17:              prev->next = cur->left;  
18:            } else{  
19:              next = cur->left;  
20:            }  
21:            prev = cur->left;  
22:          }  
23:          if (cur->right) {  
24:            if (prev != NULL) {  
25:              prev->next = cur->right;  
26:            } else {  
27:              next = cur->right;  
28:            }  
29:            prev = cur->right;  
30:          }  
31:          cur = cur->next;  
32:        }  
33:        cur = next;  
34:        prev = NULL;  
35:        next = NULL;  
36:      }  
37:    }  
38:  };  

Well, this problem still can be solve by DFS. By looking at the DFS closely, you'll find it's actually 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:      helper(root, NULL);  
13:    }  
14:    void helper(TreeLinkNode *root, TreeLinkNode *prev) {  
15:      if (root == NULL) return;  
16:      TreeLinkNode *next = NULL;  
17:      while (root) {  
18:        if (root->left) {  
19:          if (prev == NULL) next = root->left;  
20:          else prev->next = root->left;  
21:          prev = root->left;  
22:        }  
23:        if (root->right) {  
24:          if (prev == NULL) next = root->right;  
25:          else prev->next = root->right;  
26:          prev = root->right;  
27:        }  
28:        root = root->next;  
29:      }  
30:      helper(next, NULL);  
31:    }  
32:  };