Widest Binary Tree Level

Given the root of a binary tree, return the maximum width of any level in the tree.

The width of a level is defined as the number of slots between the leftmost and rightmost non-null nodes at that level (inclusive), counting the null nodes that would exist in a complete binary tree layout in between them, even if they aren't actually present in the tree. Nodes to the left of the leftmost non-null node, or to the right of the rightmost non-null node, at a given level, don't count.

Example 1

Input: [1, 3, 2, 5, 3, null, 9]

        1
       / \
      3   2
     / \   \
    5   3   9

Output: 4 — the bottom level has nodes at positions 0, 1, 3 (using 0-indexed complete-tree numbering: 5 at 0, 3 at 1, 9 at 3), so the width is 3 - 0 + 1 = 4.

Example 2

Input: [1, 3, 2, 5, null, null, 9, 6, null, 7]

Output: 7 — the last level spans from node 6 to node 7 with several null gaps counted in between.

Example 3

Input: [1] → Output: 1.

Constraints

• The number of nodes is in the range [1, 3000].
• -100 <= Node.val <= 100.
• Answers fit in a 32-bit signed integer.