499. Spreading Fire
A forest ranger models the trees of a grove as a binary tree rooted at root, where every node has a distinct integer val. At minute 0 a fire breaks out on the node whose value equals start. Each following minute the fire spreads from every burning node to all nodes directly connected to it, meaning its parent and both of its children, if they exist and are not yet burning.
Return the number of minutes that pass until the whole tree is burning. If the tree consists of the single burning node, the answer is 0. It is guaranteed that a node with value start exists.
Example 1
- Input:
- root = [6,2,8,1,4,7,9,null,null,3], start = 4
- Output:
- 4
- Explanation:
From node 4 the fire reaches 2 and 3, then 6 and 1, then 8, then 7 and 9 after the fourth minute.
Example 2
- Input:
- root = [3], start = 3
- Output:
- 0
- Explanation:
The only node is already burning at minute 0, so no time passes.
Constraints
1 ≤ number of nodes ≤ 105
1 ≤ Node.val ≤ 105, all values distinct.
A node with value start exists in the tree.
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,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)