力扣 662 ：二叉树最大宽度

✨前言

二叉树经典算法题里，最大宽度求解绝对是面试高频考点之一😯。看似只是遍历二叉树、求每层跨度，实则藏着层序遍历、完全二叉树编号规则、数值溢出优化三重核心技巧，吃透这道题，不仅能搞定算法面试，更能夯实二叉树广度优先遍历的底层思维💫。

今天就带着大家由浅入深，从解题思路、编号原理、队列实现、代码落地到数值溢出优雅优化，一次性把二叉树最大宽度解法拆解透彻📚。

🌳一、题意核心解读

首先明确题目核心规则：

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。

💡解题核心技巧：
给每个节点绑定唯一编号 → 层序遍历逐层处理 → 记录每层最左、最右编号 → 逐行计算宽度并维护全局最大值。

🚀三、层序遍历队列实现思路

想要逐层处理节点，队列结构是必不可少的载体📦，整体流程如下：

1. 队列元素封装
   不建议直接修改二叉树节点原有value值（工程化不规范，属于取巧写法）🙅。
   推荐自定义pair / 结构体，将「二叉树节点 + 节点编号」打包成一个整体存入队列，隔离业务数据与编号数据。

2. 按层遍历流程

• 初始：将根节点 + 编号 0 入队；

• 循环：队列不为空时，先记录当前队列元素个数（即当前层节点总数）；

• 逐个数出队当前层所有节点，同时将每个节点的左右子树按规则编号后入队；

• 遍历当前层时，记录本层最小编号 l和最大编号 r；

• 每层遍历结束，计算r-l+1，更新全局最大宽度。

3. 节点入队规则

• 存在左子树：左孩子编号 =父节点编号 * 2

• 存在右子树：右孩子编号 =父节点编号 * 2 + 1

💻四、基础版核心代码逻辑（伪代码示意）

// 自定义结构：封装节点 + 编号structPNI{TreeNode*node;longlongidx;};intwidthOfBinaryTree(TreeNode*root){queue<PNI>q;// 根节点编号初始为0q.push({root,0});intans=0;while(!q.empty()){// 当前层节点数量intcnt=q.size();// 记录当前层最左、最右编号longlongl=q.front().idx;longlongr=q.front().idx;// 逐层遍历for(inti=0;i<cnt;i++){autocur=q.front();q.pop();TreeNode*n=cur.node;longlongindex=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));}returnans;}

⚠️基础版存在致命缺陷：
当二叉树层数很深时，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 附近重新开始计数，数值永远不会膨胀，完美解决溢出问题✅。

🔍六、算法思维复盘与学习感悟

1. 思想迁移：把完全二叉树编号规则迁移到普通二叉树，是解题的突破口；

2. BFS 适用场景：只要涉及二叉树按层统计、每层最值、每层跨度，优先想到队列层序遍历；

3. 工程编码素养：不随意修改原节点属性，用结构体封装数据，是正规开发习惯；

4. 细节优化思维：算法不仅要能跑通，还要考虑数值范围、边界溢出、时间空间复杂度，这才是进阶必备能力💡。

很多同学觉得这类算法技巧很难，其实并非本身逻辑晦涩，而是缺少题型归纳 + 底层原理拆解。只要吃透一次编号规则、层序遍历、偏移优化这套逻辑，后续遇到同类二叉树层序问题都能举一反三🚀。