116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。示例 2:
输入：root = []
输出：[]题解[递归和迭代]
用队列来实现层序遍历节点，内存消耗很高，其实无需队列来层序遍历，通过观察可以发现，当给定当前节点cur（1）的时候，可以直接通过cur->left->next=cur->right;将左子树指向右子树（2指向3）；
那么5跟6如何连接呢？其实如果当前节点cur有指向，则表示当前节点cur不是树里面的最右边的节点（1，3，7）， if(cur->next!=NULL) cur->right->next=cur->next->left;将5指向6。
开始写递归函数层序遍历，节约queue，可是递归消耗系统栈，效果七三开。如何省略递归过程呢，实际上连接好，2-3，5-6等节点之后，就如同示例1中的FigureB,知道每层最左边的节点，就可以利用next的指向来遍历每一层的节点（即层序遍历），利用while循环和最左边节点就可以实现，可是每层最右边的节点不能通过next指向下一层，那就同样利用while循环来依次遍历每层的最左边节点，因为最左边节点的左子树就是下一层的最左边节点，所以利用left的指向来遍历每个左节点。
递归
class Solution {
public:
void work(Node*& cur){//利用递归层序遍历
if(cur->left){
cur->left->next=cur->right;//连接2-3
if(cur->next!=NULL)
cur->right->next=cur->next->left;//连接5-6
work(cur->left);
work(cur->right);
}
}
Node* connect(Node* root) {
if(root==NULL){
return root;
}
work(root);
return root;
}
};迭代
class Solution {
public:
Node* connect(Node* root) {
if(root==NULL){
return root;
}
Node* leftNode=root;//存每层最左边的节点
while(leftNode!=NULL){
Node* cur=leftNode;//通过next遍历这层
while(cur!=NULL){
if(cur->left){
cur->left->next=cur->right;//连接2-3
if(cur->next!=NULL)
cur->right->next=cur->next->left;//连接5-6
}
cur=cur->next;//往右走
}
leftNode=leftNode->left;//去下一层
}
return root;
}
};