你好！我是你的 OI 金牌教练。今天我们要深入探讨一个经典的树形结构变换问题——二叉树展开为链表。

在 NOI 竞赛中，这类题目不仅考察你对树的遍历顺序（前序、中序、后序）的理解，更考察你如何在有限的空间复杂度（原地修改）下，通过指针或数组索引巧妙地维护数据结构。这对于理解“树的线性化”以及“Morris 遍历”等进阶算法非常有帮助。

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

题目名称：二叉树展开为链表 (flatten_binary_tree) 时间限制：1.0s 内存限制：256MB

【问题描述】 给你二叉树的根节点 $root$，请你将它展开为一个单链表：

1. 展开后的单链表应该同样使用 Node 结构，其中 right 子指针指向链表中下一个节点，而 left 子指针始终为 -1（空）。
2. 展开后的单链表应该与二叉树的前序遍历顺序相同。

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

【输出格式】 输出一行，包含 $n$ 个整数，表示展开后形成的“单链表”按 right 指针顺序访问的节点值。

【样例 1 输入】

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

(注：编号 0-5 分别对应值 1, 2, 5, 3, 4, 6)

【样例 1 输出】

1 2 3 4 5 6

【数据范围】

• 节点数 $0 \le n \le 2000$
• 节点值在 $[-100, 100]$ 之间

【进阶要求】 你可以使用 $O(1)$ 额外空间（原地修改）完成展开吗？

二、 预备知识点

1. 前序遍历 (Pre-order Traversal)：根 -> 左 -> 右。
2. 树的原地修改：在不创建新节点的前提下，通过修改 L 和 R 指针改变树的结构。
3. 寻找前驱节点：对于当前节点，其前序遍历的“右子树”总是紧跟在“左子树的最右叶子节点”之后。

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

请跟我一起在草稿纸上分步推演这个过程：

1. 目标分析

我们要把这棵树变成一条“右斜线”。

    1 (root)
   / \
  2   5
 / \   \
3   4   6

展开后：1 -> 2 -> 3 -> 4 -> 5 -> 6。

2. 寻找规律（原地修改法）

观察节点 1：

• 它的左子树是 (2-3-4)，右子树是 (5-6)。
• 在前序遍历中，5 必须紧跟在 4 后面。
• 核心操作：把 1 的右子树 (5-6) 接到 1 的左子树中最右边的节点 (4) 的右边。然后把 1 的左子树挪到右边。

3. 算法步骤

• 遍历当前节点 curr。
• 如果 curr 有左孩子：
  • 找到左子树中“最右”的节点 predecessor。
  • 将 curr 的右孩子接到 predecessor 的右边。
  • 将 curr 的左孩子挪到右边，左边置为 -1。
• 继续处理下一个右孩子。

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

在 NOI 竞赛中，为了达到 $O(1)$ 额外空间，我们通常使用类似 Morris 的迭代策略。

原地展开算法流程

graph TD
    Start(开始) --> CheckEmpty{root 是否为 -1}
    CheckEmpty -- 是 --> End(结束)
    CheckEmpty -- 否 --> Init(curr 等于 root)
    Init --> WhileLoop{curr 不为 -1}
    WhileLoop -- 否 --> End
    WhileLoop -- 是 --> HasLeft{curr 有左孩子吗}
    HasLeft -- 否 --> Next(curr 等于 curr.right)
    HasLeft -- 是 --> FindPre(找到左子树最右节点 pre)
    FindPre --> Connect(将 pre.right 指向 curr.right)
    Connect --> Shift(将 curr.right 指向 curr.left)
    Shift --> Nullify(将 curr.left 设为 -1)
    Nullify --> Next
    Next --> WhileLoop

五、 复杂度分析思考过程

1. 时间复杂度分析：

   • 虽然内部有寻找 predecessor 的循环，但每条边最多被访问两次。
   • 每个节点也只会被作为 curr 访问一次。
   • 结论：时间复杂度为 $O(N)$。

2. 空间复杂度分析：

   • 递归法：由于需要递归栈，最坏情况下空间复杂度为 $O(N)$（链状树）。
   • 迭代原地修改法：只使用了常数个辅助变量（curr, pre），不消耗额外空间。
   • 结论：空间复杂度为 $O(1)$。

3. 时间复杂度优化建议：

   • 在竞赛中，如果 $N$ 很大，尽量避免递归以防系统栈溢出。
   • 原地修改法不仅节省空间，由于减少了函数调用开销，通常在常数时间上表现更优。

六、 关键读题技巧

1. 关键词：前序遍历：
   • 决定了线性化的顺序。如果你对中序或后序展开，节点连接的逻辑会完全不同。
2. 关键词：原地 (In-place)：
   • 这意味着你在读入数据到数组后，直接通过修改 L[i] 和 R[i] 的值来完成题目，不需要开辟新的空间存链表。
3. 关键词：左子针始终为 null：
   • 展开完成后，每一个节点的 L 编号必须强制设为 -1。在输出时只顺着 R 路径走。
4. 注意 N=0 的特判：
   • 空树不应有任何输出。

教练总结

这道题是结构变换的教科书级案例。在处理树的操作时，如果你能发现“某一部分必然跟在另一部分后面”的物理规律（如本题中：右子树一定跟在左子树最右侧后面），你就能写出极其精简且高效的 $O(1)$ 算法。这正是金牌选手的直觉所在。加油！