一.题目
662. 二叉树最大宽度 – 力扣（LeetCode）
二.思路讲解
2.1 思路讲解
本题要求计算二叉树的最大宽度，即每一层最左非空节点到最右非空节点之间的长度（包括中间的空节点）。 如果能够为每个节点分配一个唯一的位置编号，那么同层最右节点的编号减去最左节点的编号再加 1 就是该层的宽度。 这种编号方式可以借鉴堆的数组存储思想：假设根节点编号为 1，则左子节点编号为 2×父节点编号，右子节点编号为 2×父节点编号+1。这样，我们只需在层序遍历时，为每个节点记录其编号，并跟踪每层的最小和最大编号，即可计算宽度。
三.代码演示
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root)
{
vector<pair<TreeNode*,unsigned int>>q;//用数组模拟队列
q.push_back({root,1});
unsigned int ret = 0;
while(q.size())
{
//先更新本层宽度
auto& [x1,y1] = q[0];//获取队头
auto& [x2,y2] = q.back();//获取队尾
ret = max(ret,y2 – y1 + 1);
//让下一层入队
vector<pair<TreeNode*,unsigned int>>tmp;//临时数组
for(auto& [x,y]:q)
{
if(x->left != nullptr) tmp.push_back({x->left,y * 2});
if(x->right != nullptr) tmp.push_back({x->right,y * 2 + 1});
}
q = tmp;//更新数组
}
return ret;
}
};
四.代码讲解
一、数据结构与初始化
-
q：使用 vector<pair<TreeNode*, unsigned int>> 模拟队列，存储当前层的节点及其位置编号。根节点编号为 1。
-
ret：记录当前遇到的最大宽度，初始为 0。
二、主循环：逐层处理
当 q 非空时，表示还有节点未处理，继续循环。
1. 计算当前层宽度
-
取出当前层队列的第一个节点（即最左节点）的编号 y1。
-
取出当前层队列的最后一个节点（即最右节点）的编号 y2。
-
当前层宽度为 y2 – y1 + 1，更新全局最大值 ret。
2. 生成下一层节点
创建一个临时数组 tmp，用于存放下一层的节点及其编号。
-
遍历当前层队列的每个节点 (x, y)：
-
如果左子节点存在，则将其编号设为 y * 2，并加入 tmp。
-
如果右子节点存在，则将其编号设为 y * 2 + 1，并加入 tmp。
-
-
将 q 更新为 tmp，即进入下一层。
三、关键细节
-
编号规则：根节点编号为 1，左子节点编号为 2*父节点编号，右子节点编号为 2*父节点编号+1。这与堆的数组存储一致，能够准确反映节点的相对位置。
五、流程图
