你好！我是你的 OI 金牌教练。今天我们来学习一个经典且富有启发性的树论题目——翻转二叉树。

这道题在 LeetCode 上非常出名，而在 NOI 系列竞赛中，它是理解“递归结构自相似性”以及“树的遍历变换”的必经之路。虽然操作简单，但它能帮你建立起对树形结构进行动态修改的底层直觉。

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

题目名称：翻转二叉树 (invert_binary_tree) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一棵二叉树的根节点 $root$，请你将该二叉树进行“镜像翻转”。 镜像翻转的定义是：对于树中的每一个节点，交换其左子树和右子树。

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

【输出格式】 输出一行，包含 $n$ 个整数，表示翻转后二叉树的层序遍历序列。如果树为空，则不输出。

【样例 1 输入】

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

(注：编号 0-6 对应值 4,2,7,1,3,6,9)

【样例 1 输出】

4 7 2 9 6 3 1

【数据范围】

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

二、 预备知识点

1. 二叉树性质：理解左右孩子的对称性。
2. 递归与回溯：利用自顶向下或自底向上的逻辑处理子问题。
3. BFS (层序遍历)：利用队列进行翻转后的结果展示。
4. Swap 操作：掌握 C++ STL 中的 std::swap 或手动交换逻辑。

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

拿出一张草稿纸，我们尝试推演翻转的本质：

1. 图形化直觉

画出一个简单的二叉树：

    4
   / \
  2   7
 / \ / \
1  3 6  9

翻转操作：

• 站在节点 4 的位置，把它的两个“大手臂”（以 2 为根的子树和以 7 为根的子树）整个互换。
• 换完后，还没结束！你还得进入这两条手臂内部，把节点 2 的孩子互换，把节点 7 的孩子互换。

2. 递归的核心：自相似

• “翻转整棵树” = “交换左右孩子” + “翻转左子树” + “翻转右子树”。
• 只要一个节点不是空的，我们就对它执行这个“交换并递归”的过程。

3. 复杂度分析思考

• 时间复杂度：每个节点必须被访问一次来执行交换操作，故为 $O(N)$。
• 空间复杂度：
  • 递归取决于树高 $H$。最坏情况（链状）为 $O(N)$，平均（平衡）为 $O(\log N)$。
  • 迭代法（BFS/DFS 模拟栈）需要 $O(N)$ 的队列或栈空间。

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

在 NOI 竞赛中，递归实现最为优雅，但在处理海量数据时，迭代 BFS 也能胜任。

方案 A：递归 DFS 翻转 (自顶向下)

graph TD
    Start(开始 Invert node) --> IsNull{node 为 -1 吗}
    IsNull -- 是 --> Return(返回 -1)
    IsNull -- 否 --> SwapChild(交换 node 的 L 和 R 编号)
    SwapChild --> RecurLeft(递归处理新的左孩子 L)
    RecurLeft --> RecurRight(递归处理新的右孩子 R)
    RecurRight --> End(结束返回 node)

方案 B：迭代 BFS 翻转 (层序遍历顺便交换)

graph TD
    StartBFS(开始 BFS 翻转) --> QueueInit(将根节点入队 Q)
    QueueInit --> WhileQ{Q 不为空吗}
    WhileQ -- 否 --> EndBFS(结束)
    WhileQ -- 是 --> Pop(弹出队首节点 u)
    Pop --> SwapNode(交换 tree_u 的左孩子和右孩子)
    SwapNode --> PushLeft{左孩子存在吗}
    PushLeft -- 是 --> EnqueueL(左孩子入队 Q)
    EnqueueL --> PushRight{右孩子存在吗}
    PushLeft -- 否 --> PushRight
    PushRight -- 是 --> EnqueueR(右孩子入队 Q)
    EnqueueR --> WhileQ
    PushRight -- 否 --> WhileQ

五、 关键读题技巧

1. 关键词：翻转/镜像 (Invert/Mirror)：
   • 这类题目的核心只有两个字：交换。无论是前序遍历还是后序遍历过程中进行交换，最终结果都是等价的。
2. 关键词：每一个节点：
   • 提醒你这是一个全树的操作，不要漏掉任何一个非叶子节点。
3. 注意 $n=0$ 的特判：
   • 树为空时，递归和队列初始化都应直接跳过。
4. 空间限制 256MB：
   • 对于 $n=100$ 的数据，这非常奢侈。这意味着即使你使用再低效的容器，也不会内存溢出。重点在于逻辑的严密性。

六、 时间复杂度优化建议

• 原地翻转 (In-place)：在原有的树结构数组或指针上直接交换，不要去创建新的节点。
• 指针 vs 编号：在 C++14 竞赛中，使用 int L[MAXN], R[MAXN] 两个数组来表示左右孩子，比使用结构体指针更快且更不容易出错。
• 层序输出：翻转完成后，记得再用一个标准的 BFS 流程来输出层序遍历结果。

这就是“翻转二叉树”的全部奥秘。本质上，它是在考察你对树的递归定义的理解深度。现在，请在你的练习本上尝试写出它的 C++ 代码吧！加油！