题目描述：
给你一棵二叉树的根节点 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
题目链接：
解题主要思路：
一开始我是想用队列直接硬解，但是如果这条树每层只有最左节点和最右节点，会报错，因为内存占用太大了。后来想到，我们可以根据二叉树的特性，如果一个节点的下标为x，那么它的左右节点的下标分别为2x和2x+1。不过需要注意的是，我们需要用unsigned int来存下标的数值，因为c语言的数据存储可以看作是一个环形的存储，即使过了数据范围也无伤大雅，因为题目说了 “题目数据保证答案将会在 32 位 带符号整数范围内”，最右边节点的下标和最左边下标的差值在int的范围内，至于用unsigned是因为在leetcode中，带符号的数值类型超了范围会报错。
解题代码：
/**
* 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) {
// 数组模拟队列, 用unsigned int来计算,因为int过了数据范围会报错
vector<pair<TreeNode*, unsigned int>> que;
que.push_back(make_pair(root, 1));
unsigned int ret = 0;
while (que.size()) {
vector<pair<TreeNode*, unsigned int>> tmp;
auto& [x1, y1] = que[0];
auto& [x2, y2] = que.back();
ret = max(ret, y2-y1+1);
// 将下一层入队列
for (auto& [x, y] : que) {
if (x->left) tmp.push_back(make_pair(x->left, 2*y));
if (x->right) tmp.push_back(make_pair(x->right, 2*y+1));
}
que = tmp;
}
return ret;
}
};