A binary tree is given by its root. Find the maximum width of the tree and return it.
The width of one level is the distance from its leftmost node to its rightmost node. Count the empty places in between too, as if the tree were a full binary tree down to that level. The maximum width is the biggest width over all levels.
The answer always fits in a 32-bit signed integer.
How the judge passes the data
Examples
Example 1:
Input: root = [1,2,3,4,null,null,5]
Output: 4
Explanation: The third level has the nodes 4 and 5 with 2 empty places between them. So its width is 4.
Example 2:
Input: root = [7,3,null,5]
Output: 1
Explanation: Every level has only one node, so every width is 1.
Example 3:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 8
Explanation: The last level has 7 at the far left and 8 at the far right, with 6 empty places between them. Its width is 8.