117.填充每个节点的下一个右侧节点指针Ⅱ

难度：中等

给定一个二叉树，其定义如下：

java

class Node {
    public int val;
    public Node left;
    public Node right;
    public 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

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。

层序遍历+队列法

这道题和 102 题非常类似，只不过在单层遍历的时候需要使用虚拟头节点，并记录前一个节点，在遍历的时候让前一个节点的 next 指针指向本节点就可以了。

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

处理特例：若根节点为空，则返回空
根节点入队
BFS 循环：判断队列是否为空。如果不为空，说明还有节点需要遍历
1. 初始化当前层的节点个数 currentLevelSize 为队列的大小。
2. 使用一个虚拟头节点来实现统一操作，同时设定一个 previous 指针指向前一个节点
3. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize。
  1. 从队列中取出一个节点 current，让 previous 节点的 next 指向当前节点，并使 previous 指针指向当前节点
  2. 如果当前节点有左子节点，将左子节点入队。
  3. 如果当前节点有右子节点，将右子节点入队。
4. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数。
返回根节点：当所有层都遍历完毕后，返回原始的根节点 root。此时，树中的每个节点都已正确设置了next指针。

代码展示

java

public Node connect(Node root) {
    // 若根节点为空，则返回空
    if (root == null) {
        return null;
    }
    Deque<Node> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        // 使用虚拟头节点来实现统一操作
        Node dummy = new Node();
        Node previous = dummy;
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            Node current = queue.poll();
            previous.next = current;
            previous = current;

            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }
    return root;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点同时在 queue 中，故使用 O(n) 大小的额外空间。

层序遍历+链表法

在上述做法中，我们通过队列来获取当前层的所有节点，同时在每一层节点的遍历过程中做了两件事：

给当前层的节点进行 next 指针的连接
使用队列来存储下一层的所有节点，方便下一层的节点遍历过程

这样做时间复杂度为O(n)，然而实际上，一旦在某层的节点之间建立了 next 指针，那这层节点就形成了一个链表。

也就是说：

如果第 i 层节点之间已经建立了 next 指针，就可以通过 next 指针访问该层的所有节点，而不用再使用队列。
同时对于每个第 i 层的节点，我们又可以通过它的 left 和 right 指针知道其第 i+1 层的孩子节点是什么，所以遍历过程中就能够按顺序为第 i+1 层节点建立起 next 指针。

算法流程：

处理特例：若根节点为空，则返回空
设置当前节点：算法初始化时，设置当前节点 current 为根节点 root。这个 current 指针用于遍历树的每一层
BFS 循环：外层循环的作用是遍历树的每一层。只要 current 不为 null，就表示还有更多的层需要遍历
1. 对于每一层，首先创建一个虚拟头节点 dummy，这个节点用于从而减少一些关于空节点的判断逻辑
2. dummy.next 初始化为 null，同时设定一个 nextLayerPrevious 指针指向下一层节点的前一个节点，初始化为 dummy
3. 使用一个内层循环，利用当前层节点的 next 指针来遍历当前层的每个节点。
  1. 如果当前节点的左子节点不为空，则将左子节点连接到 nextLayerPrevious.next，这样可以确保左子节点是下一层的第一个节点。同理，如果右子节点不为空，也进行相同的操作。在连接过程中，nextLayerPrevious 不断向前移动，以保证正确连接下一层的所有节点。
  2. 完成当前层的遍历后，将 current 设置为 dummy.next，即下一层的第一个节点，然后继续执行外层循环。
返回根节点：当所有层都遍历完毕后，返回原始的根节点 root。此时，树中的每个节点都已正确设置了next指针。

代码展示

java

public Node connect(Node root) {
    // 若根节点为空，则返回空
    if (root == null) {
        return null;
    }
    Node current = root;
    // BFS 循环
    while (current != null) {
        // 虚拟头节点
        Node dummy = new Node();
        dummy.next = null;
        Node nextLayerPrevious = dummy;
        // 遍历当前层节点，为下一层节点填充next指针
        while (current != null) {
            if (current.left != null) {
                nextLayerPrevious.next = current.left;
                nextLayerPrevious = nextLayerPrevious.next;
            }
            if (current.right != null) {
                nextLayerPrevious.next = current.right;
                nextLayerPrevious = nextLayerPrevious.next;
            }
            current = current.next;
        }
        current = dummy.next;
    }
    return root;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(1)，因为这种做法没有使用队列，所以大大降低了空间复杂度。

总结

这份代码可以作为二叉树层序遍历的模板。

善用虚拟头节点能解决很多麻烦。

117.填充每个节点的下一个右侧节点指针Ⅱ ​

层序遍历+队列法 ​

代码展示 ​

层序遍历+链表法 ​

代码展示 ​

总结 ​

117.填充每个节点的下一个右侧节点指针Ⅱ

层序遍历+队列法

代码展示

层序遍历+链表法

代码展示

总结