940. Time to Burn Tree — Multi-Source BFS

Given the root of a binary tree and a list of starting node values, fire starts simultaneously at all those nodes and each minute spreads to adjacent nodes (parent and children). Return the number of minutes until the whole tree is burned. Node values are unique. The input gives a level-order tree array and the list of starting values separated by ' | '.

Input: A level-order tree array and a JSON list of start values, separated by ' | '.

Output: Integer — minutes to burn the whole tree.

Examples

Input: [1,2,3,4,5,null,6,null,null,7,8] | [4,6]
Output: 3
Explanation: Two simultaneous fires burn the tree in 3 minutes.

Input: [1,2,3] | [2,3]
Output: 1
Explanation: Fires meet at the root in 1 minute.

Input: [1] | [1]
Output: 0
Explanation: Single node already burned.

Constraints

• 1<=nodes<=10^5
• node values unique
• start values present

Asked by