Maximum Width of Binary Tree

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 extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Class TreeNode:
    val (int)
    left (TreeNode)
    right (TreeNode)

Input Format:

First Parameter - TreeNode root

Output Format:

Return the number

Example 1:

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

Example 2:

Input:
    root = [2 4 6 5 null null 3 9 null 8]
Output:
    7

Example 3:

Input:
    root = [3 11 9 5]
Output:
    2

Contraints:

• The number of nodes in the tree is the range of [1 , 3000]
• -100 <= Node.val <= 100
• Expected Time Complexity: O(N)
• Expected Space Complexity: O(N)