一、题目
1、算法题目
给定一个二叉树，填充它的每个next指针，让这个指针指向其下一个右侧节点。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给定一个二叉树
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 指针连接），'#' 表示每层的末尾。 复制代码
二、解题
1、思路分析
这一题是116题进阶而来，116题使用了层次遍历，这道题也可以使用层次遍历。
题目的题意是要求我们将二叉树的每一层节点都连接起来形成一个链表。
层次遍历是将二叉树的每一层节点取出来遍历并连接，题目要求使用常量级额外空间，可以使用递归解题。
可以初始化一个队列q，将根节点放入队列汇总，当对别不为空的时候，记录当前队列大小为n，从队列中取出n个元素并通过这n个元素拓展新的节点，如此循环，知道队列为空。
2、代码实现
代码参考：
class Solution { public Node connect(Node root) { if (root == null) { return null; } Queue<Node> queue = new LinkedList<Node>(); queue.offer(root); while (!queue.isEmpty()) { int n = queue.size(); Node last = null; for (int i = 1; i <= n; ++i) { Node f = queue.poll(); if (f.left != null) { queue.offer(f.left); } if (f.right != null) { queue.offer(f.right); } if (i != 1) { last.next = f; } last = f; } } return root; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(N)
每个节点都会被访问一次且只会被访问一次，所以时间复杂度为O(N)。
空间复杂度： O(N)
队列的空间代价为O(N)。
三、总结
因为必须要处理树上所有节点，所以时间复杂度是没有办法再降低的，可以尝试降低空间复杂度。
比如说，可以先去建立某一层的next指针，那这一层节点实际上就形成了一个链表，那么去遍历这一层，就无须再使用队列了。
基于该想法，降低空间复杂度的思路：如果第i层已经建立了next指针，就可以通过next指针访问到该层所有节点，对于i层的节点来说，又可以通过left和right指针知道其i+1层的子节点，就可以按照顺序为i+1层节点建立next指针。
