117. 填充每个节点的下一个右侧节点指针 II：利用链表结构进行树的 BFS 层序遍历.md

题目简述：

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

进阶：

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

题目链接：117. 填充每个节点的下一个右侧节点指针 II

基本解法：BFS 队列层序遍历

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

对每一层考虑虚拟首节点以简化边界处理的逻辑。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        int num = 1;
        Node prev = new Node(0);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            num--;

            prev.next = node;
            prev = node;

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);

            if (num == 0) {
                num = queue.size();
                prev = new Node(0);
            }
        }

        return root;
    }
}

进阶解法：利用链表作为队列

思路

本问题的进阶要求为：

进阶：

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

有些公司在面试时也的确要求不允许使用队列：

虾皮一面：优化，不使用其他数据结构（即不使用queue进行层序遍历）

这样的话如何处理呢？

看到 “你只能使用常量级额外空间”，是不是想到了莫里斯遍历呢？但莫里斯遍历是 DFS 中序遍历算法，本问题显然应该考虑在 BFS 的框架下实现算法，即使一定要用 DFS，也应该考虑先序遍历变体（根 → 右 → 左），中序遍历是万万不合适的。我们需要另一种方案实现避免使用显式队列。

注意到本问题中的每个节点并非只有属于二叉树的 left 指针与 right 指针，还有一个可用也是需要我们修改的 next 指针——既然有 next 指针，那么我们就完全可用把每一层的单向链表当作层序遍历队列来使用嘛！

假设当前层的 next 指针已全部更新，即当前层已经维护了一份单向链表，于是遍历该层的单向链表，修改下一层使之成为链表——即修改当前层的子节点们的 next 指针，于是下一层也维护了链表结构，我们可以移步至下一层重复该过程。这种情况下，我们实际上就是把链表当作队列在使用。

稍微一想就能够想到，本问题的所谓进阶其实并不复杂。

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

class Solution {
    public Node connect(Node root) {
        Node nextHead = null;  // 这里 next 表示下一层
        Node nextPrev = new Node(0);  // 这里 prev 表示前驱节点
        Node node = root;

        while (node != null) {
            while (node != null) {  // 或许改为 for 循环会更可读
                if (node.left != null) {
                    if (nextHead == null) nextHead = node.left;
                    nextPrev.next = node.left;
                    nextPrev = node.left;
                }

                if (node.right != null) {
                    if (nextHead == null) nextHead = node.right;
                    nextPrev.next = node.right;
                    nextPrev = node.right;
                }

                node = node.next;
            }
            
            node = nextHead;
            nextHead = null;
            nextPrev = new Node(0);
        }

        return root;
    }
}