力扣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) 。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
#define MAX_NUM 20000
int widthOfBinaryTree(struct TreeNode* root) {
// 如果根节点为空，说明是空树，其宽度为0，直接返回0
if (root == NULL) {
return 0;
}
// 定义一个数组作为队列，用于存储二叉树节点指针，实现层序遍历等操作
// 这里假设队列最多能容纳MAX_NUM个节点
struct TreeNode *q[MAX_NUM];
// 由于直接在原节点的val值上记录编号可能会超出int范围（对于某些用例），
// 所以定义一个无符号长整型数组作为辅助数组，用于记录每个节点的编号
unsigned long long Q[MAX_NUM];
// 初始化队列头部索引为0
int front = 0;
// 初始化队列尾部索引为0
int rear = 0;
// root->val = 0;
// 将根节点的编号初始化为1，存储到辅助数组Q中
Q[rear] = 1;
// 将根节点入队，作为层序遍历的起始点
q[rear++] = root;
// 初始化最大宽度为0，用于在遍历过程中记录遇到的最大宽度值
int max = 0;
// 当队列不为空时，进行层序遍历及相关计算
while (front < rear) {
// 计算当前层的宽度，这里通过每层最后一个节点的编号减去第一个节点的编号再加1来得到
// 原先是通过节点的val值来计算，但存在可能超出int范围的问题，现在使用辅助数组Q中的编号来计算
max = fmax(max, Q[rear - 1] - Q[front] + 1);
// 本层所有元素出队，同时将子节点入队，并为子节点赋值正确的编号
int curLevelSize = rear - front;
for (int i = 0; i < curLevelSize; i++) {
// 获取当前出队节点的编号
unsigned long long idx = Q[front];
// 将当前节点出队
struct TreeNode *node = q[front++];
// 如果当前节点的左子节点不为空，为左子节点计算编号并将其入队
if (node->left!= NULL) {
// 左子节点的编号为父节点编号乘以2
Q[rear] = idx * 2;
q[rear++] = node->left;
}
// 如果当前节点的右子节点不为空，为右子节点计算编号并将其入队
if (node->right!= NULL) {
// 右子节点的编号为父节点编号乘以2再加1
Q[rear] = idx * 2 + 1;
q[rear++] = node->right;
}
}
}
// 返回计算得到的二叉树的最大宽度
return max;
}