中等

问题描述

给你一棵二叉树的根节点 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

广度优先搜索

使用满二叉树编号规则对每一个节点进行编号，假设父节点编号为 $n$，那么它的左子节点的编号为 $2n - 1$，右子节点编号为 $2n$，对树进行一次层次遍历，计算出每一层最左和最右节点的距离并维护即可。但由于数据范围较大，计算过程中可能会导致数据溢出，因此可以编号时设置偏移值，或对计算结果取模。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$