479. Widest Floor
A botanist maps an orchard of connected trees, drawn as a binary tree: every node has at most a left branch and a right branch. She studies it floor by floor, where the root forms the first floor. On each floor she imagines the slots that a completely filled tree would have: if the node in slot s (counted from the left, starting at 0) has children, they sit in slots 2s and 2s+1 of the floor below, so a missing branch still reserves its slot.
The width of a floor is the number of slots from its leftmost existing node to its rightmost existing node, both included, counting the empty slots in between. Given the root of the tree as root, return the largest width found on any floor. An empty tree has width 0. The answer is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- root = [7,3,9,1,null,null,4]
- Output:
- 4
- Explanation:
The last floor has nodes in slots 0 and 3, so its width is 4, larger than the other floors.
Example 2
- Input:
- root = [10,4,12,2,6,11,15]
- Output:
- 4
- Explanation:
The tree is full, so the last floor has four nodes in slots 0 to 3 and width 4.
Example 3
- Input:
- root = [5,2,null,8]
- Output:
- 1
- Explanation:
Every floor has a single node, so the largest width is 1.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)