Return the largest width among all levels of the binary tree. A level's width spans from its leftmost present node to its rightmost present node, counting both endpoints and every missing position between them as if the tree were complete. Missing positions outside those endpoints do not contribute.
Node values do not affect the width. A level containing only one node has width 1, even if that node is far to the right in the complete-tree layout. The answer is guaranteed to fit in a signed 32-bit integer.
Input examples use a compact level-order encoding: after the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted. This compact input can omit gaps that must still be counted when measuring a level's width.
Example 1:
Input: root = [8,4,9,1,null,null,2]
Output: 4Explanation: At depth 2, the complete-tree positions are [1,null,null,2]. The two present endpoints span four positions, so the maximum width is 4.
Example 2:
Input: root = [8,null,9,null,2]
Output: 1Explanation: Each level contains only one node. Empty positions to the left of that node are outside the two endpoints and do not add to its width, so the answer is 1.
Example 3:
Input: root = [8,4,9,null,1,2]
Output: 2Explanation: The two deepest nodes occupy adjacent complete-tree positions. Their width is 2; the level above also has width 2.
Constraints:
- The tree contains between 1 and 3000 nodes.
-100 <= Node.val <= 100- The maximum width is at most 2147483647.