Imagine a binary tree drawn on a grid where every level has room for all the nodes a perfect
tree would have on that level. The width of a level is the number of grid positions from
its leftmost node to its rightmost node, counting empty positions in between. Given the
root, return the largest width of any level. Return 0 for an empty tree.
Examples
1
/ \
2 3
/ \
4 5
Input: root = build_tree([1, 2, 3, 4, None, None, 5])
Output: 4
Explanation: on the last level 4 sits in position 0 and 5 in position 3, so the width is 4.
1
/
2
/ \
3 4
Input: root = build_tree([1, 2, None, 3, 4])
Output: 2
Constraints
0 <= number of nodes <= 2000- The tree may be a chain 1000 nodes deep.
- Target complexity: O(n) time.
Goals
- Number the positions of a level as if the tree were complete
- Derive a child's position from its parent's position
- Measure width as last position minus first position plus one