力扣 662 ：二叉树最大宽度
- ✨前言
- 🌳一、题意核心解读
- 📌二、核心解题思想：借鉴完全二叉树编号规则
-
- 1. 基础编号逻辑
- 2. 层宽度计算原理
- 🚀三、层序遍历队列实现思路
- 💻四、基础版核心代码逻辑（伪代码示意）
- ✨五、进阶优化：编号偏移缩范围，彻底解决数值溢出
-
- 1. 溢出根源分析
- 2. 优化核心思想
- 3. 优化后核心编号规则
- 🔍六、算法思维复盘与学习感悟
✨前言
二叉树经典算法题里，最大宽度求解绝对是面试高频考点之一😯。看似只是遍历二叉树、求每层跨度，实则藏着层序遍历、完全二叉树编号规则、数值溢出优化三重核心技巧，吃透这道题，不仅能搞定算法面试，更能夯实二叉树广度优先遍历的底层思维💫。
今天就带着大家由浅入深，从解题思路、编号原理、队列实现、代码落地到数值溢出优雅优化，一次性把二叉树最大宽度解法拆解透彻📚。
🌳一、题意核心解读
首先明确题目核心规则：
二叉树最大宽度：指每一层最左侧有效节点到最右侧有效节点之间的节点总数；
⚠️关键规则：中间空缺的空节点，也要计入宽度计算；
最终答案：取二叉树所有层宽度中的最大值，即为整棵树的最大宽度。
普通深度遍历很难直接统计每层左右边界，而层序遍历（BFS） 天然按层处理节点，是解这道题的最优选择✅。
📌二、核心解题思想：借鉴完全二叉树编号规则
1. 基础编号逻辑
我们都知道完全二叉树有经典编号规律：
-
若父节点编号为 i
-
左子树编号：2 * i
-
右子树编号：2 * i + 1
为了计算更简洁，我们从 0 开始给根节点编号🌱：
-
根节点编号：0
-
左孩子：2 * i
-
右孩子：2 * i + 1
2. 层宽度计算原理
对二叉树每一层而言：
单层宽度 = 本层最大编号 – 最小编号 + 1
举个实例🌰：
-
第一层：最小编号 0，最大编号 0 → 宽度 0-0+1 = 1
-
第二层：最小编号 0，最大编号 1 → 宽度 1-0+1 = 2
-
第三层：最小编号 0，最大编号 3 → 宽度 3-0+1 = 4
整棵树最大宽度即为 4。
💡解题核心技巧： 给每个节点绑定唯一编号 → 层序遍历逐层处理 → 记录每层最左、最右编号 → 逐行计算宽度并维护全局最大值。
🚀三、层序遍历队列实现思路
想要逐层处理节点，队列结构是必不可少的载体📦，整体流程如下：
队列元素封装 不建议直接修改二叉树节点原有 value 值（工程化不规范，属于取巧写法）🙅。 推荐自定义pair / 结构体，将「二叉树节点 + 节点编号」打包成一个整体存入队列，隔离业务数据与编号数据。
按层遍历流程
-
初始：将根节点 + 编号 0 入队；
-
循环：队列不为空时，先记录当前队列元素个数（即当前层节点总数）；
-
逐个数出队当前层所有节点，同时将每个节点的左右子树按规则编号后入队；
-
遍历当前层时，记录本层最小编号 l 和最大编号 r；
-
每层遍历结束，计算 r-l+1，更新全局最大宽度。
-
存在左子树：左孩子编号 = 父节点编号 * 2
-
存在右子树：右孩子编号 = 父节点编号 * 2 + 1
💻四、基础版核心代码逻辑（伪代码示意）
// 自定义结构：封装节点 + 编号
struct PNI {
TreeNode* node;
long long idx;
};
int widthOfBinaryTree(TreeNode* root) {
queue<PNI> q;
// 根节点编号初始为0
q.push({root, 0});
int ans = 0;
while(!q.empty()) {
// 当前层节点数量
int cnt = q.size();
// 记录当前层最左、最右编号
long long l = q.front().idx;
long long r = q.front().idx;
// 逐层遍历
for(int i = 0; i < cnt; i++) {
auto cur = q.front();
q.pop();
TreeNode* n = cur.node;
long long index = cur.idx;
// 更新当前层最右编号
r = index;
// 左子树入队
if(n->left)
q.push({n->left, index * 2});
// 右子树入队
if(n->right)
q.push({n->right, index * 2 + 1});
}
// 维护全局最大宽度
ans = max(ans, (int)(r – l + 1));
}
return ans;
}
⚠️基础版存在致命缺陷： 当二叉树层数很深时，index * 2 会急剧膨胀，超出整型甚至长整型的表示范围，引发运行时溢出报错，这也是很多同学提交代码超时、runtime 错误的根本原因❗。
✨五、进阶优化：编号偏移缩范围，彻底解决数值溢出
1. 溢出根源分析
每层子节点编号依赖父节点编号逐级翻倍，层数越多，编号数值越大，最终超出数据类型存储上限。
但我们真正需要的不是绝对编号，而是同层节点之间的相对差值📌。 只要保证同层节点的编号相对顺序不变，整体做数值偏移，完全不影响宽度计算结果。
2. 优化核心思想
每层遍历开始时，记录当前层最小编号 l； 计算下一层子节点编号时，做偏移处理：
-
左子树新编号：(父节点编号 – l) * 2
-
右子树新编号：(父节点编号 – l) * 2 + 1
原理：把当前层的最小编号虚拟当作 0，整体向左平移，强行压缩编号数值范围，从根源杜绝溢出问题🌊。
3. 优化后核心编号规则
原本：
左 = index * 2
右 = index * 2 + 1
优化后：
左 = (index – l) * 2
右 = (index – l) * 2 + 1
经过偏移后，每层编号都会从 0 附近重新开始计数，数值永远不会膨胀，完美解决溢出问题✅。
🔍六、算法思维复盘与学习感悟
思想迁移：把完全二叉树编号规则迁移到普通二叉树，是解题的突破口；
BFS 适用场景：只要涉及二叉树按层统计、每层最值、每层跨度，优先想到队列层序遍历；
工程编码素养：不随意修改原节点属性，用结构体封装数据，是正规开发习惯；
细节优化思维：算法不仅要能跑通，还要考虑数值范围、边界溢出、时间空间复杂度，这才是进阶必备能力💡。
很多同学觉得这类算法技巧很难，其实并非本身逻辑晦涩，而是缺少题型归纳 + 底层原理拆解。只要吃透一次编号规则、层序遍历、偏移优化这套逻辑，后续遇到同类二叉树层序问题都能举一反三🚀。
