Given the root of a binary tree, compute the maximum width among all levels of the tree.

The width of a level is defined as the number of positions between the leftmost and rightmost non null nodes at that level, inclusive. When measuring width, treat the tree as if it were a complete binary tree, so missing children between existing nodes still count as positions.

Return the maximum width over all levels.

Note: Null nodes at the ends of a level are not counted, but null positions between two non null nodes are counted.

Constraints:

• The number of nodes in the tree is in the range $[1, 3000]$

• $-100 \leq$ Node.val $\leq 100$

Input: root = [1,3,2,5,3,null,9]-TreeNode
Output: 4-int
Explanation: Using level-order positions (treating the tree as complete), level 0 [1] has width 1, level 1 [3, 2] has width 2, and level 2 [5, 3, null, 9] has its leftmost non-null node at position 0 and rightmost at position 3, giving width 3 - 0 + 1 = 4 (the maximum).

Input: root = [1,3,2,5,null,null,9,6,null,null,7]-TreeNode
Output: 8-int
Explanation: At the deepest relevant level, the leftmost non-null node (6) and rightmost non-null node (7) are far apart when counting “missing” positions in between (as in a complete binary tree). Their indices span 8 positions inclusive, so the maximum width is 8.

Input: root = [1,3,2,5]-TreeNode
Output: 2-int
Explanation: Level 0 [1] has width 1, level 1 [3, 2] has width 2 (the maximum), and level 2 [5, null] has only one non-null node, so its width is 1 (nulls at the end don’t increase width).

Input: root = [1]-TreeNode
Output: 1-int
Explanation: Only one node exists, so the only level has width 1.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.