862. Find Maximum Width of Binary Tree

Given the root of a binary tree, return its maximum width — the maximum number of nodes spanning any single level, counting the gaps (null positions) between the leftmost and rightmost non-null nodes of that level. Positions are assigned as in a complete tree. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Integer — the maximum width.

Examples

Input: [1,3,2,5,3,null,9]
Output: 4
Explanation: The bottom level spans 4 positions.

Input: [1]
Output: 1
Explanation: Single node.

Input: []
Output: 0
Explanation: Empty tree.

Constraints

• 0<=nodes<=3000
• -1000<=value<=1000

Asked by