目录
力扣662. 二叉树最大宽度
难度 中等
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
输入：root = [1,3,2,5,3,null,9] 输出：4 解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
输入：root = [1,3,2,5,null,null,9,6,null,7] 输出：7 解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
输入：root = [1,3,2,5] 输出：2 解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
- 树中节点的数目范围是
[1, 3000] -100 <= Node.val <= 100
/**
* 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) {
}
};解析代码
第一种思路（会超过内存限制）： 既然统计每一层的最大宽度，我们优先想到的就是利用序遍历，把当前层的结点全部存在队列里面，利用队列的长度来计算每一层的宽度，统计出最大的宽度。 但是由于空节点也是需要计算在内的。因此可以选择将空节点也存在队列里面。 这个思路是我们正常会想到的思路，但是极端境况下，最左边一条长链，最右边一条长链，需要存几亿个空节点，会超过最大内存限制。
第二种思路（利用二叉树的顺序存储 - 通过根节点的下标，计算左右孩子的下标）：
依旧是利用层序遍历，但是这一次队列里面不单单存结点信息，并且还存储当前结点如果在数组中存储所对应的下标（学习数据结构：堆的时候，学过计算左右孩子的方式）。
这样我们计算每一层宽度的时候，无需考虑空节点，只需将当层结点的左右结点的下标相减再加 1 即可，因为要用左右结点，所以可以考虑用vector数组模拟queue队列。
但是这里有个细节问题：如果二叉树的层数非常恐怖的话，任何一种数据类型都不能存下下标的值。但是没有问题，因为数据的存储是一个环形的结构。并且题目说明，数据的范围在 int 这个类型的最大值的范围之内，因此不会超出一圈。因此，如果是求差值的话，我们无需考虑溢出的情况。（用unsigned int即可）
/**
* 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, 0}); // 数组右边进，左边出
unsigned int ret = 0;
while(!q.empty())
{
// 先更新这⼀层的宽度
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 + 1});
if(x->right != nullptr)
tmp.push_back({x->right, y * 2 + 2});
}
q = tmp;
}
return ret;
}
};
