你好，同学！这道题目是“树型结构”与“链表思想”结合的典范。在 NOI 竞赛中，虽然我们习惯用数组模拟树，但理解这种通过指针构建“横向联系”的技巧，对于解决复杂的动态规划（如树形 DP 的层间转移）非常有启发。

这道题的进阶要求是 $O(1)$ 的额外空间，这正是区分“普通选手”和“金牌选手”的关键。

一、 题目描述 (NOI 格式)

题目名称： 填充每个节点的下一个右侧节点指针 II (Populating Next Right Pointers in Each Node II) 时间限制： 1.0s 内存限制： 256MB

【问题描述】 给定一个二叉树，结构定义如下：

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

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

【输入格式】 输入一棵二叉树的层序遍历序列（空位用 null 表示）。在 NOI 测评中，你将直接实现核心逻辑函数。

【输出格式】 输出填充好 next 指针后的树。测评系统将通过每层 next 指针形成的链表来验证正确性。

【样例 1 输入】

1 2 3 4 5 null 7

【样例 1 输出】

1
2 3
4 5 7

【样例 2 输入】

1 2 3 4 null null 5

【样例 2 输出】

1
2 3
4 5

【数据范围】

• 树中节点数目在 $[0, 6000]$ 范围内。
• $-100 \le Node.val \le 100$
• 进阶要求：使用 $O(1)$ 额外空间（递归栈空间不计入）。

二、 预备知识点

1. 二叉树遍历变体：理解如何利用已有的信息（上一层的 next 指针）来辅助当前层的遍历。
2. 链表技巧（虚拟头节点）：使用 dummyHead 简化链表插入逻辑。
3. 迭代与指针操作：在不借助队列的情况下实现层序扫描。

三、 启发式思路引导：草稿纸上的推理

第一步：常规 BFS 的局限

如果我们使用 std::queue，空间复杂度是 $O(W)$（$W$ 是树的最大宽度），在 $N=6000$ 时虽然能过，但不符合进阶要求的 $O(1)$。

第二步：寻找“现成的路”

观察题目：当我们处理第 $H$ 层时，第 $H-1$ 层的 next 指针已经全部连接好了。

• 启发：第 $H-1$ 层现在不仅是一棵树，它还是一个单链表！
• 动作：我们可以像遍历链表一样遍历第 $H-1$ 层，同时把它们的左右子节点（即第 $H$ 层的节点）顺手连起来。

第三步：利用虚拟头节点 (Dummy Head)

在处理每一层时，这一层链表的“头”可能很深（比如根节点没有左孩子）。

• 技巧：每层开始前，在草稿纸上画一个“虚拟节点” dummy。
• 逻辑：用一个指针 tail 指向 dummy。遍历上一层时，每发现一个子节点，就执行 tail->next = 子节点; tail = tail->next;。
• 切换：当上一层遍历完，下一层的链表也就接好了。下一层的起点就是 dummy->next。

四、 算法流程图 (伪代码提示)

为了符合 Mermaid 语法并避免报错，我们使用文字描述逻辑。

graph TD
    Start("开始: connect(root)") --> RootNull{"root 为空?"}
    RootNull -- "是" --> Return("返回 root")
    RootNull -- "否" --> InitCur("curr 指针指向 root")
    
    InitCur --> OuterLoop{"curr 不为空?"}
    OuterLoop -- "否" --> Return
    
    OuterLoop -- "是" --> LayerInit("创建 dummy 节点; 创建 tail 指针指向 dummy")
    LayerInit --> InnerLoop{"curr 不为空?"}
    
    InnerLoop -- "是" --> CheckLeft{"curr 左孩子存在?"}
    CheckLeft -- "是" --> LinkLeft("tail 指向 next 设为 curr 左孩子; tail 移动到 tail 指向 next")
    LinkLeft --> CheckRight
    CheckLeft -- "否" --> CheckRight{"curr 右孩子存在?"}
    
    CheckRight -- "是" --> LinkRight("tail 指向 next 设为 curr 右孩子; tail 移动到 tail 指向 next")
    LinkRight --> MoveNext
    CheckRight -- "否" --> MoveNext("curr 移动到 curr 指向 next (同层移动)")
    
    MoveNext --> InnerLoop
    
    InnerLoop -- "否" --> SwitchLayer("curr 更新为 dummy 指向 next (切到下一层)")
    SwitchLayer --> OuterLoop

五、 复杂度分析思考过程

1. 时间复杂度：
   • 每个节点只被访问两次：一次作为“当前层”被遍历，一次作为“下一层”被连接。
   • 总代价为 $O(N)$。
2. 空间复杂度：
   • 我们只使用了 curr, dummy, tail 这几个指针。
   • 没有使用队列或递归栈，因此是真正的 $O(1)$ 额外空间。

六、 总结：读题关键词与易错点

1. 关键词：

   • “Next Right Pointer”：这意味着层序关系是核心。
   • “Each Node II” (非完全二叉树)：说明节点可能缺失，不能简单通过 curr->left->next = curr->right 来处理。必须动态寻找“下一个可用的子节点”。
   • “Constant Extra Space”：这是最高频的考点，提示你放弃 queue，转而利用已建立的 next 链表。

2. 常见错误：

   • 忽略空层：在移动到下一层时（curr = dummy->next），如果没有子节点了，dummy->next 会是 NULL，此时外层循环应正确终止。
   • 忘记重置 Dummy：每一层都需要一个新的 dummy（或者重置 dummy->next = NULL），否则会把不同层的节点连在一起。
   • 指针悬挂：在连接时，要确保 tail 始终指向当前层已连接的最后一个节点。

这道题是练习多指针联动的极佳教材。在 NOI 中，掌握这种“原地修改结构”的能力，能帮你省下大量的内存空间！加油！