# 117. 填充每个节点的下一个右侧节点指针 II

``````/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
Node* connect(Node* root) {
//类似于之前的玩法，只是需要加一些额外的判断。
//层序遍历还是照怼
queue q;
if(root != NULL){
q.push(root);
}
Node* temp = root;
while(!q.empty()){
int size = q.size();

for(int i = 0; i < size; i++){
root = q.front();
q.pop();
if(!q.empty())
root->next = q.front();
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
}
return temp;
}
};``````

[1,2,3,4,5,null,7]

[1,#,2,3,4,5,7,#,4,5,7,#]

[1,#,2,3,#,4,5,7,#]

``````/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
Node* connect(Node* root) {
//类似于之前的玩法，只是需要加一些额外的判断。
//层序遍历还是照怼
queue q;
if(root != NULL){
q.push(root);
}
Node* temp = root;
while(!q.empty()){
int size = q.size();

for(int i = 0; i < size; i++){
root = q.front();
q.pop();
if(i != size - 1)root->next = q.front();
//这里泥马的又一次利用了队列是否为空，来判断当前层是否遍历完成。
//梅开二度，和上次一样的毛病
if(root->left)q.push(root->left);
if(root->right)q.push(root->right);
}
}
return temp;
}
};``````

//这里泥马的又一次利用了队列是否为空，来判断当前层是否遍历完成。
//梅开二度，和上次一样的毛病

``````/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
Node* connect(Node* root) {
Node* temp = root;
Node* first = root;
bool update = false;
while(first != NULL && (first->left != NULL || first->right != NULL || first->next != NULL)){
while(1){
if(root->left != NULL && root->right != NULL){
if(update == false){
update = true;
first = root->left;
}
root->left->next = root->right;
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL){
root->right->next = help->left;
root = help;
break;
}
else if(help->right != NULL){
root->right->next = help->right;
root = help;
break;
}
}
if(help->next == NULL){
//走到头了
break;
}
}
else if(root->left != NULL && root->right == NULL){
if(update == false){
update = true;
first = root->left;
}
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL){
root->left->next = help->left;
root = help;
break;
}
else if(help->right != NULL){
root->left->next = help->right;
root = help;
break;
}
}
if(help->next == NULL){
//走到头了
break;
}
}
else if(root->left == NULL && root->left != NULL){
if(update == false){
update = true;
first = root->right;
}
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL){
root->right->next = help->left;
root = help;
break;
}
else if(help->right != NULL){
root->right->next = help->right;
root = help;
break;
}
}
if(help->next == NULL){
//走到头了
break;
}
}
else{//两个儿子都是空的
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL || help->right != NULL){
root = help;
break;
}
}
if(help->next == NULL){
//说明到头了
break;
}
}
}
//这一层结束了，需要更新点东西：
if(update == false)return temp;
update = false;
root = first;
}
return temp;
}
};

[3,9,20,null,null,15,7]

[3,#,9,20,#,15,#]

[3,#,9,20,#,15,7,#]``````

``````/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
Node* connect(Node* root) {
Node* temp = root;
Node* first = root;
bool update = false;
while(first != NULL && (first->left != NULL || first->right != NULL || first->next != NULL)){
while(1){
if(root->left != NULL && root->right != NULL){
if(update == false){
update = true;
first = root->left;
}
root->left->next = root->right;
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL){
root->right->next = help->left;
root = help;
break;
}
else if(help->right != NULL){
root->right->next = help->right;
root = help;
break;
}
}
if(root->left != NULL && root->right != NULL && root->left->next == root->right && help->next == NULL){
//走到头了
break;
}
if((root->left == NULL || root->right == NULL) && root->next == NULL){
//上边的if只包含了两个儿子均不为空的情况要break，
//并没有把只剩下单个儿子的情况给列出来，需要重新写一个
break;
}
}
else if(root->left != NULL && root->right == NULL){
if(update == false){
update = true;
first = root->left;
}
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL){
root->left->next = help->left;
root = help;
break;
}
else if(help->right != NULL){
root->left->next = help->right;
root = help;
break;
}
}
if(!(help->left != NULL&& help->right != NULL) && help->next == NULL){
//走到头了
break;
}
}
else if(root->left == NULL && root->right != NULL){
if(update == false){
update = true;
first = root->right;
}
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL){
root->right->next = help->left;
root = help;
break;
}
else if(help->right != NULL){
root->right->next = help->right;
root = help;
break;
}
}
if(!(help->left != NULL&& help->right != NULL) && help->next == NULL){
//走到头了
break;
}
}
else{//两个儿子都是空的
Node* help = root;
while(help->next != NULL){
help = help->next;
if(help->left != NULL || help->right != NULL){
root = help;
break;
}
}
if(!(help->left != NULL&& help->right != NULL) && help->next == NULL){
//说明到头了
//这里要对update更新！！！！！！！！！
if(help->right != NULL){
update = true;
first = root->right;
}
if(help->left != NULL){
update = true;
first = root->left;
}
break;
}
}
}
//这一层结束了，需要更新点东西：
if(update == false)return temp;
update = false;
root = first;
}
return temp;
}
};``````

``````class Solution {
public:
void handle(Node* &last, Node* &p, Node* &nextStart) {
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}

Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) {
if (p->left) {
handle(last, p->left, nextStart);
}
if (p->right) {
handle(last, p->right, nextStart);
}
}
start = nextStart;
}
return root;
}
};

``````/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
void point(Node* &last,Node* &p, Node* &nextFirst){
if(last){
last->next = p;
}
if(nextFirst == nullptr){
nextFirst = p;
}
last = p;
}
Node* connect(Node* root) {
Node* first = root;
while(first){
Node* last = nullptr;
Node* nextFirst = nullptr;
for(Node* i = first; i != nullptr; i = i->next){
if(i->left)point(last, i->left, nextFirst);
if(i->right)point(last, i->right, nextFirst);
}
first = nextFirst;
}
return root;
}
};``````