你好！我是你的OI竞赛教练。这道题（LeetCode 662. Maximum Width of Binary Tree）是非常经典的一道结合了二叉树遍历与完全二叉树索引性质的题目。在NOI体系下，我们需要将其转化为一道标准的算法题，并注意其中隐含的“数据溢出”陷阱。

下面我将把这道题改写为NOI风格，并带你一步步拆解思路。

---

一、 题目描述

题目名称： 二叉树最大宽度 (Maximum Width of Binary Tree)

【题目描述】

给定一棵二叉树的根节点（编号为 1），请编写程序计算该树的最大宽度。

为了计算二叉树的宽度，我们定义如下规则：

1. 我们将这棵二叉树视为一棵满二叉树（Full Binary Tree），即假设每一个父节点都拥有两个子节点，不存在的节点用 null（空）填充。
2. 每一层的宽度定义为：该层中，最左边的非空节点与最右边的非空节点之间（包含这两个端点）所有节点（含 null 节点）的长度。
3. 整棵树的最大宽度是所有层中宽度的最大值。

通俗地讲，如果我们给满二叉树的节点进行编号（根节点为 1，左孩子为 $2 \times i$，右孩子为 $2 \times i + 1$），那么每一层的宽度就是：（该层最右侧非空节点的编号 - 该层最左侧非空节点的编号 + 1）。

【输入格式】 第一行包含一个整数 $N$ ($1 \le N \le 3000$)，表示二叉树的节点总数。节点编号从 $1$ 到 $N$，且 1 号节点始终为根节点。 接下来 $N$ 行，第 $i$ 行包含两个整数 $L_i, R_i$，分别表示第 $i$ 号节点的左孩子编号和右孩子编号。

• 如果 $L_i = 0$，表示没有左孩子。
• 如果 $R_i = 0$，表示没有右孩子。

【输出格式】 输出一个整数，表示二叉树的最大宽度。

【样例数据】

样例 1

输入：

6
2 3
4 5
0 6
0 0
0 0
0 0

对应树结构示意： (注：输入只给结构，不给节点值，这里为了理解，假设节点编号即为位置)

       1
     /   \
    2     3
   / \     \  
  4   5     6 

• 第 1 层：节点 1，宽度 1
• 第 2 层：节点 2, 3，宽度 2
• 第 3 层：节点 4, 5, (null), 6。最左是4，最右是6。中间虽空缺，但宽度为 index(6) - index(4) + 1 = 4。

输出：

4

---

样例 2

输入：

4
2 0
3 4
0 0
0 0

对应树结构示意：

       1
     / 
    2  
   / \ 
  3   4

• 第 3 层节点为 3 和 4，宽度为 2。

输出：

2

---

样例 3

输入：

4
2 3
4 0
0 0
0 0

对应树结构示意：

       1
     /   \
    2     3
   /
  4

• 第 2 层宽度为 2 (2和3)。
• 第 3 层宽度为 1 (只有4)。
• 最大宽度为 2。

输出：

2

---

【数据说明与提示】

1. 数据范围：$1 \le N \le 3000$。
2. 特殊情况：
   • 虽然节点数较少，但树的结构可能非常特殊（如退化成一条链）。
   • 树的深度可能达到 $N$，直接使用完全二叉树的下标计算（$2^N$）会导致数值溢出，请务必考虑下标的重置或相对偏移处理。
3. 答案范围：题目保证最终的最大宽度在 32 位有符号整数范围内。

• 注意： 虽然节点数不多，但树的深度可能会很深，直接计算节点索引可能会导致数值溢出。

---

二、 预备知识点总结

在攻克这道题之前，你需要掌握以下知识点：

1. 二叉树的遍历（BFS/DFS）： 能够熟练使用 std::queue 进行广度优先搜索（层序遍历），或者使用递归进行深度优先搜索。
2. 堆式编号（Heap Indexing）： 在完全二叉树中，如果父节点的下标是 $i$，那么：
   • 左孩子下标为 $2 \times i$
   • 右孩子下标为 $2 \times i + 1$
3. 大数处理与相对索引： 理解 unsigned long long 的使用，或者利用相对偏移量解决深度过大导致的下标溢出问题。
4. C++ STL 使用： std::pair, std::queue, std::vector 的基本操作。

---

三、 启发式教学与思路推演

来，拿出你的草稿纸，我们把这道题的思考过程画出来。

1. 怎么定义“宽度”？（画图理解）

学生：教练，那个 null 也要算宽度，怎么数呢？ 教练：好问题。不要去想“数空节点”，太麻烦。我们用坐标轴的思想。

• 想象根节点在坐标 1。
• 它的左孩子在 2，右孩子在 3。
• 下一层左孩子的左孩子在 4...

草稿纸演练：

         1 (index: 1)
       /   \
      2     3 (index: 2, 3)
     / \   / \
    4   5 6   7 (index: 4, 5, 6, 7)

如果某些节点不存在，比如节点 3 没了，那么 6和7的位置也就空着，但是如果有节点 2 的右孩子 5，它的下标依然通过 2 * 2 + 1 = 5 算出来。

结论 1： 每一层的宽度 = 该层最右侧非空节点的下标 - 该层最左侧非空节点的下标 + 1。

2. 怎么遍历？（选择算法）

学生：我可以用 DFS 吗？ 教练：可以，DFS 需要记下每一层最先访问到的那个节点（最左节点）的下标。当你遍历到该层其他节点时，用当前下标减去最左下标。 不过，求“最大宽度”通常和“层”有关，BFS（广度优先搜索） 会更直观，因为 BFS 天然就是一层一层处理的。

3. 致命陷阱：数据溢出（重点！）

学生：题目说节点数最多 3000，我用 int 存下标可以吗？ 教练：停！这是最大的陷阱。

• 如果树退化成一条链（全往左偏或全往右偏），深度可达 3000。
• 第 3000 层的下标是多少？是 $2^{3000}$。
• long long 最大才 $2^{63}$ 左右。$2^{3000}$ 绝对爆掉了！

学生：那怎么办？写高精度？ 教练：不需要。注意题目只要宽度，不需要真实的绝对坐标。

• 假设第 100 层，最左边节点下标是 $100000000000$，最右边是 $100000000005$。宽度是 6。
• 如果我们把这一层最左边的节点重新标记为 $0$，那最右边就是 $5$。宽度还是 $5 - 0 + 1 = 6$。

优化策略（缩点法）： 在 BFS 进行下一层扩展时，我们可以把当前层的下标进行重置。 为了防止下一层溢出，我们可以让下一层的下标计算基于：当前节点下标 - 当前层第一个节点的下标。 或者更粗暴一点：使用 unsigned long long，利用它的自然溢出特性。在 C++ 中，unsigned 类型减法即使溢出，只要两数实际差值在表示范围内，结果依然是正确的（补码特性）。

最稳妥的NOI写法： 每次入队下一层节点时，将下标更新为：index = index - current_level_min_index。这样每层的下标都从 0 或 1 开始，永远不会溢出。

---

4. 时空复杂度分析

• 时间复杂度： 我们需要遍历每个节点一次，所以是 $O(N)$。
• 空间复杂度： 使用队列存储一层节点，最坏情况下（比如最后一层最宽）约为 $N/2$，所以是 $O(N)$。

---

四、 伪代码逻辑流程图 (Mermaid)

这是基于 BFS 和下标重置策略的伪代码流程。

flowchart TD
    Start((开始)) --> CheckRoot{根节点为空?}
    CheckRoot -- 是 --> Ret0[返回 0]
    CheckRoot -- 否 --> InitQueue[初始化队列 Q]
    
    InitQueue --> PushRoot[入队: node=root, index=1, maxWidth=0]
    
    LoopStart{队列不为空?} -- 否 --> End((结束, 返回 maxWidth))
    LoopStart -- 是 --> LevelInit[获取当前层节点数 size]
    
    LevelInit --> GetBase[记录当前层第一个节点的 index 为 baseIndex]
    
    InnerLoop{遍历当前层 size 次} -- 完成 --> LoopStart
    InnerLoop -- 进行中 --> PopNode[取出队首节点 currNode, currIndex]
    
    PopNode --> CalcWidth[更新 maxWidth = max of maxWidth, currIndex - baseIndex + 1]
    
    CalcWidth --> CheckLeft{有左孩子?}
    CheckLeft -- 是 --> PushLeft[左孩子入队<br/>下标: 2 * (currIndex - baseIndex)]
    CheckLeft -- 否 --> CheckRight
    
    PushLeft --> CheckRight{有右孩子?}
    CheckRight -- 是 --> PushRight[右孩子入队<br/>下标: 2 * (currIndex - baseIndex) + 1]
    CheckRight -- 否 --> NextIter[继续下一次循环]
    
    NextIter --> InnerLoop
    
    style Start fill:#f9f,stroke:#333
    style End fill:#9f9,stroke:#333
    style CalcWidth fill:#ff9,stroke:#333

代码提示 (C++14 Hint):

// 核心数据结构提示
struct NodeInfo {
    TreeNode* node;
    unsigned long long index; // 使用ull防止意外，配合减法策略
};
queue<NodeInfo> q;

// 关键逻辑
unsigned long long current_id = q.front().index;
unsigned long long base_id = q.front().index; // 当前层基准
// 入队逻辑示例
// q.push({node->left, 2 * (current_id - base_id)}); 
// q.push({node->right, 2 * (current_id - base_id) + 1});

---

五、 读题理解关键词总结

做这类题目时，要在读题阶段圈出以下关键词：

1. “最大宽度” (Maximum Width)： 看到这个词，立马反应：是求某一层最左和最右的距离，而不是这层有多少个节点。
2. “所有节点（含 null 节点）”： 这暗示了我们需要使用满二叉树的索引机制（$i, 2i, 2i+1$），而不是简单的计数。
3. “节点范围 [1, 3000]” + “二叉树”： 小数据范围通常是诱饵。结合二叉树性质，必须思考“链状树”带来的深度爆炸问题（$2^{3000}$ 溢出风险）。
4. “返回整数”： 最终答案在 Integer 范围内，说明虽然中间坐标可能很大，但宽度的结果是可控的。

希望这个思路能帮你彻底搞懂这道题！试着自己在纸上推导一下样例 2 的坐标变化，然后去实现代码吧。加油！