给你一棵二叉树的根节点 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 20000int widthOfBinaryTree(struct TreeNode* root) {// 如果根节点为空，说明是空树，其宽度为0，直接返回0if (root == NULL) {return 0;}// 定义一个数组作为队列，用于存储二叉树节点指针，实现层序遍历等操作// 这里假设队列最多能容纳MAX_NUM个节点struct TreeNode *q[MAX_NUM];// 由于直接在原节点的val值上记录编号可能会超出int范围（对于某些用例），// 所以定义一个无符号长整型数组作为辅助数组，用于记录每个节点的编号unsigned long long Q[MAX_NUM];// 初始化队列头部索引为0int front = 0;// 初始化队列尾部索引为0int 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) {// 左子节点的编号为父节点编号乘以2Q[rear] = idx * 2;q[rear++] = node->left;}// 如果当前节点的右子节点不为空，为右子节点计算编号并将其入队if (node->right!= NULL) {// 右子节点的编号为父节点编号乘以2再加1Q[rear] = idx * 2 + 1;q[rear++] = node->right;}}}// 返回计算得到的二叉树的最大宽度return max;
}