给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
示例 1：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
示例 2：
输入：root = [] 输出：[]
提示：
-
树中的节点数在范围
[0, 6000]内 -
-100 <= Node.val <= 100
进阶：
-
你只能使用常量级额外空间。
-
使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。
这道题和 116. Populating Next Right Pointers in Each Node 算是姊妹题。
最简单的方式，使用 Deque 来保存每一层节点，然后建立起来"连接"。但是，很明显，这种方案不符合空间复杂度要求。
基于上面这种解法，再深入思考一步，上面使用 Deque 就是想要保存接下来需要访问的元素，并且保存访问的前后顺序。现在 Node 上有 next 字段，可以利用这个字段，打通这条链表，遍历上一层时，打通下一次的链接结构。这里需要保存的就有两点：
-
这条链表的头结点，用于下一层的遍历；
-
这条链表的尾节点，用于添加下一个节点。
这道题的思路和 116. Populating Next Right Pointers in Each Node 思路几乎是一样的：在上层遍历中，建立下一层的链接。
但这道题和 116. Populating Next Right Pointers in Each Node 在于：116 是完全二叉树，那么可以直接使用 next 节点的 left 子节点。这道题不是一个完全二叉树，所以，就需要在运动中寻找不为空的节点。另外，最左节点的选择，也不能直接使用 mostLeft.left，也是需要在运动中去寻找下一层第一个不为空的节点。两道题区别不大只是需要多注意细节。
这样，把第一种解法的代码稍作修改就可以了。
看题解，别人大部分是用了两层循环，外层是负责向下推进，内层负责同层向右。D瓜哥用了一层循环来遍历每个节点。
- 一刷
-
link:{sourcedir}/_0117_PopulatingNextRightPointersInEachNodeII.java[role=include] - 二刷
-
link:{sourcedir}/_0117_PopulatingNextRightPointersInEachNodeII_2.java[role=include] - 二刷（优化）
-
link:{sourcedir}/_0117_PopulatingNextRightPointersInEachNodeII_21.java[role=include] - 三刷
-
link:{sourcedir}/_0117_PopulatingNextRightPointersInEachNodeII_3.java[role=include]