# 【leetcode】Populating Next Right Pointers in Each Node II

Question：

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example, Given the following binary tree,

```         1
/  \
2    3
/ \    \
4   5    7```

After calling your function, the tree should look like:

```         1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL```

Anwser 1：

```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root){
return;
}

while(cur != NULL){     // find last right node (left or right)
if(cur->left) {
p = cur->left;
break;
}
if(cur->right){
p = cur->right;
break;
}
cur = cur->next;
}

if(root->right){
root->right->next = p;
}

if(root->left){
root->left->next = root->right ? root->right : p;
}

connect(root->right);   // from right to left
connect(root->left);
}
};```

1） list为非完美二叉树，右分支可能为空，因此从right -> left 遍历

2） 从最右分支开始查找，且root没有 left 节点，则找 right 节点

Anwser 2：

```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root){
return;
}

queue<TreeLinkNode *> Q;    // save one line root(s)
queue<TreeLinkNode *> Q2;   // save next one line root(s), swap with Q
Q.push(root);

while(!Q.empty()){
Q.pop();

if(tmp->left) Q2.push(tmp->left);
if(tmp->right) Q2.push(tmp->right);

if(Q.empty()){
tmp->next = NULL;
queue<TreeLinkNode*> tmpQ = Q;  // swap queue
Q = Q2;
Q2 = tmpQ;
} else {
tmp->next = Q.front();
}
}
}
};```

1） 新增一个Q2队列，保存下一行的全部元素，辅助判断是最后一个元素（Q为空）则置为NULL

2） queue队列实现比递归要好

Anwser 3：

```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root){
return;
}

queue<TreeLinkNode *> Q;    // save one line root(s)
Q.push(root);
Q.push(NULL);       // flag

while(!Q.empty()){
Q.pop();

if(tmp != NULL){        // check flag
if(tmp->left) Q.push(tmp->left);
if(tmp->right) Q.push(tmp->right);
tmp->next = Q.front();
} else {
if(Q.empty()){      // pop flag = NULL, then check is empty
break;
}
Q.push(NULL);
}
}
}
};```

0 条评论

• ### 【leetcode】Populating Next Right Pointers in Each Node

Populate each next pointer to point to its next right node. If there is no next ...

• ### 【leetcode】Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

• ### 【leetcode】Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

• ### 【leetcode】Populating Next Right Pointers in Each Node

Populate each next pointer to point to its next right node. If there is no next ...

• ### Populating Next Right Pointers in Each Node

问题：将二叉树的所有结点指向他的右边的一个结点 分析：对于每一个结点来说，其操作都是一样的，除了他的左儿子指向右儿子外，其左儿子的全部右后辈均指向其右儿子的全部...

• ### 【leetcode】Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

• ### Centos7 下安装 RabbitMQ

其中APPLICATIONS DISABLED 标示是必须要安装的，另外两个项目可以忽略 jinterface : Java compiler disable...