LeetCode: Populating Next Right Pointers in Each Node II

这题关键是要记录下一层第一个节点

 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     TreeLinkNode *nextright(TreeLinkNode *root) {
12         while (root) {
13             if (root->left) return root->left;
14             if (root->right) return root->right;
15             root = root->next;
16         }
17         return NULL;
18     }
19     void connect(TreeLinkNode *root) {
20         if (!root) return;
21         TreeLinkNode *second, *first;
22         first = root;
23         second = NULL;
24         first->next = NULL;
25         while (first) {
26             if (first->left) {
27                 if (!second) second = first->left;
28                 if (first->right) first->left->next = first->right;
29                 else first->left->next = nextright(first->next);
30             }
31             if (first->right) {
32                 if (!second) second = first->right;
33                 first->right->next = nextright(first->next);
34             }
35             first = first->next;
36             if (!first) {
37                 first = second;
38                 second = NULL;
39             }
40         }
41     }
42 };

如果可以用extra 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         queue<TreeLinkNode *> S;
13         if (!root) return;
14         S.push(root);
15         S.push(NULL);
16         while (!S.empty()) {
17             TreeLinkNode *front = S.front();
18             S.pop();
19             if (!front) continue;
20             front->next = S.front();
21             if (front->left) S.push(front->left);
22             if (front->right) S.push(front->right);
23             if (!S.front()) S.push(NULL);
24         }
25     }
26 };