LeetCode: Populating Next Right Pointers in Each Node

思路对的，少数次过，基本一次过吧

 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         // Start typing your C/C++ solution below
13         // DO NOT write int main() function
14         queue<TreeLinkNode *> S;
15         queue<TreeLinkNode *> T;
16         if (!root) return;
17         S.push(root);
18         while (!S.empty()) {
19             TreeLinkNode *tmp = S.front();
20             S.pop();
21             if (tmp->left || tmp->right) {
22                 T.push(tmp->left);
23                 T.push(tmp->right);
24             }
25             if (!S.empty()) tmp->next = S.front();
26             else tmp->next = NULL;
27             if (S.empty()) {
28                 while (!T.empty()) {
29                     S.push(T.front());
30                     T.pop();
31                 }
32             }
33         }
34     }
35 };

贴一段后来写的更加好的代码

 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         // Start typing your C/C++ solution below
13         // DO NOT write int main() function
14         if (!root) return;
15         queue<TreeLinkNode*> S, T;
16         S.push(root);
17         while (!S.empty()) {
18             while (!S.empty()) {
19                 TreeLinkNode *tmp = S.front();
20                 S.pop();
21                 if (tmp->left) T.push(tmp->left);
22                 if (tmp->right) T.push(tmp->right);
23                 tmp->next = S.empty()? NULL : S.front();
24             }
25             S.swap(T);
26         }
27     }
28 };