你好！我是你的 OI 金牌教练。今天我们来研究二叉树的一种高级变换操作——填充每个节点的下一个右侧节点指针。

这道题在 LeetCode 中是第 116 题。在 NOI 竞赛中，它考察的不仅是基本的树遍历，更重要的是考察你对树层级结构特性的洞察力，以及如何利用已有信息进行空间优化达到 $O(1)$ 的额外空间复杂度。

一、 题目描述 (NOI 规范版)

题目名称：填充每个节点的下一个右侧节点指针 (populating_next_right_pointers) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个 完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

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

【输入格式】 输入文件包含多行，描述二叉树的结构。 第一行一个整数 $n$，表示节点总数。 接下来的 $n$ 行，每行描述一个节点的信息：首先是该节点的值 $v$，然后是该节点的左子节点编号 $L$，最后是右子节点编号 $R$。 （注：节点编号从 0 到 $n-1$，根节点固定为 0。保证给定的是一棵完美二叉树。）

【输出格式】 输出包含 $L$ 行（$L$ 为树的层数）。 每行按从左到右的顺序输出该层节点的 next 指针链条指向的节点值。

【样例 1 输入】

7
1 1 2
2 3 4
3 5 6
4 -1 -1
5 -1 -1
6 -1 -1
7 -1 -1

【样例 1 输出】

1
2 3
4 5 6 7

【数据范围】

• 树中节点的数量为 $2^h - 1$，其中 $h$ 是树的高度。
• $0 \le n \le 4095$ (即高度不超过 12)
• 每个节点的值在 $[-1000, 1000]$ 之间。

【进阶要求】

• 你能使用 $O(1)$ 额外空间完成吗？（递归栈空间不计入额外空间）

二、 预备知识点

1. 完美二叉树 (Perfect Binary Tree)：理解其结构对称性，每层节点数固定。
2. 层序遍历 (Level Order Traversal)：基础的 BFS 思路。
3. 链表连接思想：将同一层的节点看作一个单链表。
4. 空间优化：利用已经建立的 next 指针来遍历当前层，从而推导出下一层的 next 关系。

三、 启发式思维导图：教练的草稿纸

请跟我一起在草稿纸上分步推演，尤其是如何不使用队列（Queue）完成分层连接：

1. 核心矛盾：跨越“家族”的连接

在一个节点内部，连接 left 和 right 很简单。 但如何连接节点 A 的 right 和节点 B 的 left（其中 A, B 是兄弟）？ 洞察：如果父层已经连接好了，我们可以通过 parent.next 找到邻居。

2. 原地修改的逻辑演进

• 假设第 $i$ 层已经全部连接好了。
• 我们站在第 $i$ 层的第一个节点 leftmost。
• 遍历第 $i$ 层的链表：
  • 连接当前节点 curr 的左儿子到右儿子：curr.left.next = curr.right
  • 连接当前节点 curr 的右儿子到邻居的左儿子：curr.right.next = curr.next.left (如果 curr.next 存在)
• 处理完一层，移动到下一层的 leftmost。

3. 复杂度预估

• 时间复杂度：每个节点访问常数次，$O(N)$。
• 空间复杂度：由于只使用了几个辅助指针，额外空间为 $O(1)$。

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

在 NOI 竞赛中，为了冲击高分，我们需要展示对 $O(1)$ 空间算法的掌握。

迭代法：利用已建立的 Next 指针连接

graph TD
    Start(开始) --> CheckRoot{根节点是否存在}
    CheckRoot -- 否 --> End(结束)
    CheckRoot -- 是 --> InitLeft(leftmost 等于 根节点)
    InitLeft --> WhileLevel(循环: leftmost.left 是否存在)
    WhileLevel -- 否 --> End
    WhileLevel -- 是 --> InitCurr(curr 等于 leftmost)
    InitCurr --> WhileRow(内层循环: curr 不为空)
    WhileRow -- 否 --> MoveDown(leftmost 等于 leftmost.left)
    MoveDown --> WhileLevel
    WhileRow -- 是 --> Conn1(连接 curr 的左子到右子)
    Conn1 --> HasNext{curr.next 是否存在}
    HasNext -- 是 --> Conn2(连接 curr 的右子到邻居的左子)
    HasNext -- 否 --> NextNode(curr 等于 curr.next)
    Conn2 --> NextNode
    NextNode --> WhileRow

五、 复杂度分析思考过程

1. 时间复杂度分析：

   • 外层循环控制层数，层数为 $\log N$。
   • 内层循环遍历每一层的节点，总节点数为 $N$。
   • 每个连接操作都是常数级。
   • 结论：总时间复杂度为 $O(N)$。

2. 空间复杂度分析：

   • BFS/队列法：队列中最多存储一层节点，对于完美二叉树，最后一层有 $N/2$ 个节点，空间为 $O(N)$。
   • 指针迭代法：仅使用了 leftmost 和 curr 两个指针变量。
   • 结论：空间复杂度为 $O(1)$（不计输出存储）。

3. 优化建议：

   • 由于是完美二叉树，不存在“左虚右实”的情况，可以极大简化判断逻辑。
   • 在读入数据时，建议使用结构体数组存储，避免频繁的 new 操作。

六、 关键读题技巧

1. 关键词：完美二叉树：
   • 这是最重要的提示！意味着 left 存在则 right 必存在，且所有路径长度相同。不用处理复杂的非对称逻辑。
2. 关键词：常量级额外空间：
   • 看到这个词，应立刻警惕“不能直接使用标准 BFS 队列”。
3. 关键词：next 指针：
   • 这既是题目要求的目标，也是解题的工具。
4. 注意输入格式转换：
   • LeetCode 给出的是数组序列化，但在 NOI 考场上，数据通常以节点列表形式给出。建立 tree[i].left 等索引映射是第一步。

教练总结

这道题是**“利用已知信息构建未知信息”**的典范。通过上一层已经打通的 next 隧道，我们能轻松地为下一层铺路。在竞赛中，当你发现当前问题的解依赖于同层邻居的信息时，不妨思考一下：是否可以先处理上一层，再利用上一层的横向联系来解决当前层的问题？加油！