Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree are also counted into the length calculation.
It is guaranteed that the answer will fit in a 32-bit signed integer.
Example 1:
Input: root = [1, 3, 2, 5, 3, null, 9]
Output: 4
Explanation: The maximum width exists at level 2 with nodes [5, 3, null, 9], so the width is 4.
Example 2:
Input: root = [1, 3, 2, 5, null, null, 9, 6, null, 7]
Output: 7
Explanation: The maximum width exists at level 3 with nodes [6, null, null, null, null, null, 7], so the width is 7.
Example 3:
Input: root = [1, 3, 2, 5]
Output: 2
Explanation: The maximum width exists at level 1 with nodes [3, 2], so the width is 2.
[1, 3000]-100 <= Node.val <= 100