Maximum Width of Binary Tree

Medium

Given the root of a binary tree, return the maximum width. The width of a level is the number of positions between its leftmost and rightmost non-null nodes (as if the level were a full binary tree), counting the null slots between them.

Example 1

Input:  root = [1,3,2,5,3,null,9]
Output: 4

Example 2

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

Constraints

• 1 <= number of nodes <= 3000
• -100 <= Node.val <= 100