# Populating Next Right Pointers in Each Node

> Given a binary tree

>```
}
```
> Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

> Initially, all next pointers are set to NULL.

> Note:

> You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
After calling your function, the tree should look like:
```
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
```

+ 如果一个子节点是根节点的左子树，那么它的next就是该根节点的右子树，譬如上面例子中的4，它的next就是2的右子树5。
+ 如果一个子节点是根节点的右子树，那么它的next就是该根节点next节点的左子树。譬如上面的5，它的next就是2的next（也就是3）的左子树。

```c++
class Solution {
public:
if(!root) {
return;
}

while(p) {
//记录下层第一个左子树
if(!first) {
first = p->left;
}
//如果有左子树，那么next就是父节点
if(p->left) {
p->left->next = p->right;
} else {
//叶子节点了，遍历结束
break;
}

//如果有next，那么设置右子树的next
if(p->next) {
p->right->next = p->next->left;
p = p->next;
continue;
} else {
//转到下一层
p = first;
first = NULL;
}
}
}
};
```

# Populating Next Right Pointers in Each Node II

> 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
```

```c++
class Solution {
public:
if(!root) {
return;
}

while(p) {
//设置下层第一个元素
if(!first) {
if(p->left) {
first = p->left;
} else if(p->right) {
first = p->right;
}
}

if(p->left) {
//如果有last，则设置last的next
if(last) {
last->next = p->left;
}
//last为left
last = p->left;
}

if(p->right) {
//如果有last，则设置last的next
if(last) {
last->next = p->right;
}
//last为right
last = p->right;
}

//如果有next，则转到next
if(p->next) {
p = p->next;
} else {
//转到下一层
p = first;
last = NULL;
first = NULL;
}
}
}
};
```